Sort Array by Order Defined by Another Array

Sorting array A so that its elements follow the sequence defined in array B is a frequency-counting and traversal problem that shows up regularly in placement coding rounds.

The problem appears under several names: “sort by reference array”, “order array by another array”, “custom sort using a second array”. The core requirement stays the same: print elements from A in the order they appear in B, then print whatever remains in A at the end.

This article covers two standard approaches, their time complexities, and code in Python and Java.

Problem Statement and Worked Example

Given two arrays, arr1 (the array to reorder) and arr2 (the reference sequence), the output must satisfy:

• All elements matching arr2[0] appear first, repeated as many times as they occur in arr1
• Then all elements matching arr2[1], and so on through arr2
• Elements from arr1 with no match in arr2 are sorted and appended last

Manual Verification

Before writing code, confirming the expected output by hand takes about a minute and catches boundary-condition bugs before they reach test cases.

• arr1: {3, 6, 13, 3, 9, 10, 14, 6, 9, 13}
• arr2: {6, 3, 9, 13, 10}

Step	arr2 element	Frequency in arr1	Added to output
1	6	2	6, 6
2	3	2	3, 3
3	9	2	9, 9
4	13	2	13, 13
5	10	1	10
—	14 (not in arr2)	1	14 (sorted, appended last)

Output: {6, 6, 3, 3, 9, 9, 13, 13, 10, 14}

The element 14 is in arr1 but absent from arr2, so it lands at the end. The GeeksforGeeks article on this problem also describes a custom-comparator approach where arr2 index positions serve as the sort key, which is useful background if the interviewer asks for a third method.

Method 1: Binary Search Approach

Sort arr1 first, then use binary search to locate and extract each arr2 element.

Algorithm

• Sort arr1 in ascending order
• Maintain a working copy of the sorted arr1 to track which elements remain
• For each element target in arr2:
  • Use binary search to find the leftmost and rightmost positions of target in the working copy
  • Append all elements in that range to the result
  • Delete them from the working copy
• Append the remaining elements from the working copy to the result (already sorted)

Python Code

import bisect

def sort_by_order_binary_search(arr1, arr2):
    arr1 = sorted(arr1)        # O(n log n)
    remaining = arr1[:]        # working copy
    result = []

    for target in arr2:
        lo = bisect.bisect_left(remaining, target)
        hi = bisect.bisect_right(remaining, target)
        result.extend(remaining[lo:hi])   # all copies of target
        del remaining[lo:hi]              # mark used

    result.extend(remaining)   # leftover elements are already sorted
    return result

arr1 = [3, 6, 13, 3, 9, 10, 14, 6, 9, 13]
arr2 = [6, 3, 9, 13, 10]
print(sort_by_order_binary_search(arr1, arr2))
# Output: [6, 6, 3, 3, 9, 9, 13, 13, 10, 14]

Python’s bisect module handles the binary search. bisect_left returns the leftmost position where target fits in the sorted array; bisect_right returns the rightmost. The slice between them contains every copy of target.

Complexity

• Time: O(n log n) to sort arr1; O(m log n) for m binary searches. Total: O((n + m) log n)
• Space: O(n) for the sorted working copy

The del remaining[lo:hi] step shifts list elements, adding O(n) per deletion in the worst case. For placement-test discussions, O(n log n) is the accepted answer for this method.

Method 2: Hashing Approach

Build a frequency map of arr1 first, then output elements in arr2’s order.

Algorithm

• Count the frequency of every element in arr1 using a hashmap
• For each element target in arr2:
  • If target is in the map, append it freq[target] times to the result
  • Remove target from the map
• Collect remaining map entries, sort their keys, and append all copies to the result

Python Code

from collections import Counter

def sort_by_order_hash(arr1, arr2):
    freq = Counter(arr1)     # O(n)
    result = []

    for target in arr2:      # O(m)
        if target in freq:
            result.extend([target] * freq[target])
            del freq[target]

    # Remaining elements: sort by key, append all copies
    for val in sorted(freq):           # O(r log r)
        result.extend([val] * freq[val])

    return result

arr1 = [3, 6, 13, 3, 9, 10, 14, 6, 9, 13]
arr2 = [6, 3, 9, 13, 10]
print(sort_by_order_hash(arr1, arr2))
# Output: [6, 6, 3, 3, 9, 9, 13, 13, 10, 14]

Python’s collections.Counter builds the frequency map in one call. Counter(arr1) returns a dictionary-like object where each key is a unique value from arr1 and each value is its count.

Java Code

import java.util.*;

public class SortByOrder {
    public static List<Integer> sortByOrder(int[] arr1, int[] arr2) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int val : arr1) {
            freq.put(val, freq.getOrDefault(val, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        for (int target : arr2) {
            if (freq.containsKey(target)) {
                int count = freq.get(target);
                for (int i = 0; i < count; i++) {
                    result.add(target);
                }
                freq.remove(target);
            }
        }

        // Remaining elements — TreeMap iterates keys in ascending order
        for (Map.Entry<Integer, Integer> entry : new TreeMap<>(freq).entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
}

The Java version uses a TreeMap for the remaining entries to avoid a separate sort step. TreeMap iterates keys in ascending order by default, so the leftover elements come out sorted without an extra Collections.sort() call.

Complexity

• Time: O(n) to build the frequency map; O(m) to traverse arr2; O(r log r) to sort r leftover elements. Total: O(n + m + r log r)
• Space: O(n) for the frequency map

For arrays where most arr1 values appear in arr2, r is small and the sort cost is negligible. This is the faster method for most inputs.

Comparing the Two Approaches

Property	Binary Search	Hashing
Time complexity	O((n + m) log n)	O(n + m + r log r)
Space complexity	O(n)	O(n)
Handles duplicates	Yes	Yes
Requires arr1 sorted first	Yes	No
Best case: large arr1, small arr2	Slower (must sort all of arr1)	Faster
Expected answer in coding interviews	As warm-up alternative	Standard

Both methods produce identical output. The hashing method is the expected answer at product-company coding rounds because it avoids sorting arr1 upfront. The binary search method is worth presenting as the intuitive first approach when an interviewer asks for a naive solution before the optimised one.

For related array problems that use the same scan-and-compare traversal pattern, see find the equilibrium index of an array. For problems that use hashmaps to identify relationships between array elements, see find all symmetric pairs in an array. For a breakdown of why both approaches here use O(n) space for different reasons, see space complexity of algorithms with examples.

Where This Problem Appears in Placement Tests

AMCAT and CoCubes coding rounds for IT service companies include array ordering problems because they test two skills together: array traversal and hashmap construction. The canonical example above is a standard fixture; placement test variants include:

• Returning the result array instead of printing it
• Arrays where arr2 contains elements not in arr1 at all (tests the guard condition)
• Arrays where arr1 has no duplicates (simpler frequency map, same structure)
• Requiring leftover elements to remain in their original unsorted order

The guard condition if target in freq is the most common mistake point. Candidates who skip it produce a KeyError at runtime when an arr2 element has no match in arr1. The second most common error is sorting arr1 in-place before building the frequency map in the hashing method. It works correctly for this problem but modifies the caller’s original array as a side effect, which breaks any code that reuses arr1 later.

The count-once, look-up-many pattern from the hashing approach transfers into AI pipeline work: token frequency maps, embedding lookup tables, and key-value caches in attention mechanisms all exploit O(1) retrieval from a prebuilt map. TinkerLLM at ₹299 connects those placement-prep data structures to working LLM pipeline exercises, starting from the same building blocks this problem uses.