Relative Sort Array: Custom Ordering with Counting

You are given two arrays, arr1 and arr2, where arr2 contains distinct elements that are all present in arr1. Sort the elements of arr1 so that the relative ordering of items matches arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

This is LeetCode 1122: Relative Sort Array, and it is a great exercise in custom sorting with frequency counting. The technique it teaches -- counting occurrences and using a reference array to define order -- comes up whenever you need to sort data by an externally defined priority.

Why this problem matters

Most sorting problems ask you to sort by value. This one asks you to sort by position in another array. That shift in perspective is what makes it interesting. You are not comparing elements against each other. You are mapping each element to a priority defined by arr2, then placing them in that priority order.

This pattern appears in real-world scenarios: sorting search results by a priority list, ordering database rows by a custom enum, or arranging UI elements according to a user-defined preference. The underlying idea is always the same -- count what you have, then lay it out in the order someone else specifies.

The key insight

Rather than writing a custom comparator, you can solve this in two clean passes:

1. Count frequencies in arr1. Build a map of how many times each value appears.
2. Iterate through arr2 in order. For each value, append it to the result as many times as its count indicates, then remove it from the map.
3. Collect the leftovers. Any values still in the map were not in arr2. Sort them and append them to the end.

This avoids the overhead of a comparison-based sort for the arr2 portion entirely. You are essentially doing a counting sort guided by arr2's ordering.

The solution

from collections import Counter

def relative_sort_array(arr1: list[int], arr2: list[int]) -> list[int]:
    count = Counter(arr1)
    result = []

    for val in arr2:
        result.extend([val] * count.pop(val))

    for val in sorted(count):
        result.extend([val] * count[val])

    return result

Let's walk through the logic.

First, we build a frequency map of every element in arr1 using Counter. This tells us exactly how many of each value we need to place.

Next, we iterate through arr2 in order. For each value, count.pop(val) retrieves its frequency and removes it from the map in one step. We then extend the result with that many copies of the value. Because we iterate arr2 from left to right, the result naturally respects arr2's ordering.

After processing all of arr2, whatever remains in the count map consists of elements that were not in arr2. We sort those remaining keys and append each value the appropriate number of times. This satisfies the requirement that leftover elements appear in ascending order at the end.

Visual walkthrough

Let's trace through the example with arr1 = [2,3,1,3,2,4,6,7,9,2,19] and arr2 = [2,1,4,3,9,6].

Notice how the first loop handles all the elements that appear in arr2, placing them in arr2's exact order. The second loop just sweeps up whatever is left and sorts it. Two simple passes, no custom comparator needed.

Complexity analysis

Time is O(n log n) where n is the length of arr1. Building the frequency map is O(n). Iterating through arr2 and placing elements is O(n) total across all values. The O(n log n) term comes from sorting the remaining elements that were not in arr2. In the worst case, no elements appear in arr2, and you sort the entire array.

Space is O(n) for the frequency map and the result array. The Counter stores at most n entries (if all elements are distinct), and the result array has exactly n elements.

The building blocks

1. Frequency counting with a hash map

The first building block is counting occurrences. This is the foundation of counting sort and appears in dozens of LeetCode problems.

from collections import Counter
count = Counter(arr1)

A single line gives you a dictionary mapping each value to its frequency. You can also build this manually with a loop if you want to be explicit:

count = {}
for val in arr1:
    count[val] = count.get(val, 0) + 1

2. Custom ordering with a reference lookup

The second building block is using one sequence to define the ordering of another. The pattern is: iterate the reference in order, pull from your data for each entry.

for val in arr2:
    result.extend([val] * count.pop(val))

This pattern generalizes to any problem where you need to reorder data according to an external priority list. The key detail is using pop to consume each entry so you know exactly what remains afterward.

Edge cases

Before submitting, think through these scenarios:

• arr2 contains all elements of arr1: The second loop has nothing to process. The result is fully determined by arr2's ordering.
• arr2 is empty: Every element is "remaining." The result is just arr1 sorted in ascending order.
• All elements in arr1 are the same: The frequency map has one entry. If that value is in arr2, it gets placed first. Otherwise, it goes into the sorted remainder.
• arr1 has elements with very high frequency: The extend call handles this naturally -- it just appends the value that many times.
• Single-element arrays: Both arr1 = [1] and arr2 = [1] produce [1]. Trivial, but good to verify your code handles it without index errors.

From understanding to recall

You have seen how counting frequencies and iterating a reference array produces the correct custom sort. The code is short -- barely ten lines -- and the logic is clean. But in an interview, the difference between "I know this" and "I can write this" is everything.

The tricky part is not the algorithm. It is remembering the details: using pop to consume entries, calling sorted(count) on the remaining keys, and knowing that extend is the right tool for appending multiple copies. These are small decisions that add up, and they are easy to fumble under pressure.

Spaced repetition locks them in. You practice writing the frequency counting step, the reference-ordered placement loop, and the sorted remainder sweep from memory. After a few rounds, the whole solution flows out naturally. You see "sort by a custom ordering" in a problem statement, and the two-pass pattern is already at your fingertips.

Related posts

• Sort Colors - Another custom sorting problem using the Dutch national flag partitioning technique
• Top K Frequent Elements - Frequency counting combined with bucket sort to find the most common elements
• Group Anagrams - Hash map grouping where sorted character signatures serve as keys

CodeBricks breaks Relative Sort Array into its frequency counting and reference-ordered placement building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a custom sorting problem appears in your interview, you do not hesitate. You just write it.