LeetCode 1122 - Relative Sort Array

LeetCode Problem 1122

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Counting Sort

Solution

Problem Understanding

This problem asks us to sort arr1, but not in ordinary ascending or descending order. Instead, the sorting order is partially dictated by another array, arr2.

The key requirement is that every number appearing in arr2 must appear in arr1 in exactly the same relative order. If a number appears multiple times in arr1, all of its occurrences should be grouped together according to the order defined by arr2.

For example, if arr2 = [2,1,4,3,9,6], then all 2s in arr1 must come first, followed by all 1s, then all 4s, then all 3s, and so on. The number of occurrences must remain unchanged.

After placing all numbers that appear in arr2, any remaining numbers in arr1 that are not listed in arr2 should be appended to the end in normal ascending order.

The input consists of two integer arrays:

• arr1, the array we must rearrange.
• arr2, which defines the custom ordering.

The problem guarantees several important properties. Every element in arr2 is distinct, meaning no duplicates appear in the ordering array. Also, every element in arr2 is guaranteed to exist in arr1, so we never need to worry about missing values.

The constraints are relatively small:

• Both arrays have at most 1000 elements.
• Values are bounded between 0 and 1000.

These constraints suggest that even moderately inefficient approaches may pass, but there is an opportunity to exploit the small value range for a cleaner and more efficient solution.

Several edge cases are worth identifying early. arr1 may contain many repeated values, so frequency tracking is important. arr2 might cover nearly all of arr1, leaving only a few leftover elements to sort. In another case, arr2 may cover only a small subset of arr1, meaning many elements need to be appended in ascending order. We also need to correctly handle duplicate values that are not in arr2.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly scan arr1 for every number in arr2.

For each number in arr2, we traverse arr1 and collect all matching elements into the result. After processing every value in arr2, we scan arr1 again to collect elements not present in arr2, sort those leftovers, and append them.

This works because it explicitly enforces the relative ordering defined by arr2. Every matching element is gathered in the required sequence, and all remaining numbers are sorted separately.

However, this approach performs unnecessary repeated scans of arr1. If arr2 has length m and arr1 has length n, we may scan the full array m times, leading to O(n × m) time complexity. While acceptable for the given constraints, it is inefficient compared to what is possible.

Key Insight for an Optimal Solution

The important observation is that we only care about how many times each number appears.

Since the values are constrained to the range [0, 1000], we can count the frequency of each number in arr1. Once we know how many times each value appears, constructing the answer becomes simple.

We first process numbers in arr2 order. For each number, we append it to the result as many times as its frequency indicates.

Afterward, we iterate through all possible values from 0 to 1000. Any remaining frequencies correspond to numbers not included in arr2, and we append them in ascending order.

This approach avoids repeated scans and naturally preserves the required ordering.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m + n log n)	O(n)	Repeatedly scans arr1, then sorts leftovers
Optimal	O(n + k)	O(k)	Uses counting sort idea, where k = 1001

Here, n = len(arr1) and k = 1001, the maximum possible value range.

Algorithm Walkthrough

1. Create a frequency array of size 1001, initialized to 0. Since values are guaranteed to be between 0 and 1000, we can directly use each value as an index.
2. Traverse arr1 and count how many times each number appears. For every number x, increment frequency[x].
3. Initialize an empty result array.
4. Process every number in arr2 in order. For each number:

• Look up its frequency.
• Append that number to the result exactly that many times.
• Reset its frequency to 0 so it is not processed again later.

5. Iterate through every value from 0 to 1000.

• If a value still has a positive frequency, it means it was not present in arr2.
• Append it to the result according to its count.

6. Return the completed result array.

Why it works

The algorithm works because it partitions elements into two categories. Numbers appearing in arr2 are emitted first and in exactly the order dictated by arr2. Their multiplicities are preserved through frequency counting. Any numbers not in arr2 remain in the frequency array and are emitted later in increasing numerical order. Since every element is processed exactly according to the problem rules, the final array is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        frequency = [0] * 1001

        # Count occurrences of each number
        for number in arr1:
            frequency[number] += 1

        result = []

        # Add numbers according to arr2 order
        for number in arr2:
            result.extend([number] * frequency[number])
            frequency[number] = 0

        # Add remaining numbers in ascending order
        for number in range(1001):
            if frequency[number] > 0:
                result.extend([number] * frequency[number])

        return result

The implementation begins by creating a fixed-size frequency array. Because the constraints limit values to 0 through 1000, indexing directly into an array is more efficient than using a hash map.

The first loop counts how many times each number appears in arr1. This transforms the problem from rearranging elements to reconstructing them from frequencies.

The second loop processes arr2 in the exact required order. For each number, we append it multiple times according to its count. Resetting the frequency to 0 ensures it will not accidentally appear again during the final ascending pass.

Finally, we iterate from 0 to 1000. Any remaining frequencies represent numbers not included in arr2, so appending them in ascending order satisfies the second requirement of the problem.

Go Solution

func relativeSortArray(arr1 []int, arr2 []int) []int {
	frequency := make([]int, 1001)

	// Count occurrences of each number
	for _, num := range arr1 {
		frequency[num]++
	}

	result := make([]int, 0, len(arr1))

	// Add numbers according to arr2 order
	for _, num := range arr2 {
		for frequency[num] > 0 {
			result = append(result, num)
			frequency[num]--
		}
	}

	// Add remaining numbers in ascending order
	for num := 0; num <= 1000; num++ {
		for frequency[num] > 0 {
			result = append(result, num)
			frequency[num]--
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version but differs in a few implementation details. Since Go does not support Python-style list multiplication, repeated elements are added using loops. The result slice is preallocated with capacity len(arr1) to reduce reallocations. Because integers remain very small and bounded by the constraints, integer overflow is not a concern.

Worked Examples

Example 1

Input:

arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]

Step 1: Build Frequency Table

Number	Count
1	1
2	3
3	2
4	1
6	1
7	1
9	1
19	1

Step 2: Process arr2

Current Number	Frequency	Result
2	3	[2,2,2]
1	1	[2,2,2,1]
4	1	[2,2,2,1,4]
3	2	[2,2,2,1,4,3,3]
9	1	[2,2,2,1,4,3,3,9]
6	1	[2,2,2,1,4,3,3,9,6]

Step 3: Add Remaining Numbers

Remaining frequencies are:

7 → 1
19 → 1

Final result:

[2,2,2,1,4,3,3,9,6,7,19]

Example 2

Input:

arr1 = [28,6,22,8,44,17]
arr2 = [22,28,8,6]

Step 1: Build Frequency Table

Number	Count
6	1
8	1
17	1
22	1
28	1
44	1

Step 2: Process arr2

Current Number	Frequency	Result
22	1	[22]
28	1	[22,28]
8	1	[22,28,8]
6	1	[22,28,8,6]

Step 3: Add Remaining Numbers

Remaining numbers:

17, 44

Final result:

[22,28,8,6,17,44]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	Count elements in arr1, process arr2, then scan value range
Space	O(k)	Frequency array of fixed size 1001

Here, n is the size of arr1 and k = 1001 is the fixed numeric range. Since k is constant, the algorithm effectively runs in linear time relative to the input size.

Test Cases

solution = Solution()

# Example 1 from problem statement
assert solution.relativeSortArray(
    [2,3,1,3,2,4,6,7,9,2,19],
    [2,1,4,3,9,6]
) == [2,2,2,1,4,3,3,9,6,7,19]

# Example 2 from problem statement
assert solution.relativeSortArray(
    [28,6,22,8,44,17],
    [22,28,8,6]
) == [22,28,8,6,17,44]

# Single element array
assert solution.relativeSortArray(
    [5],
    [5]
) == [5]  # Minimum input size

# All elements controlled by arr2
assert solution.relativeSortArray(
    [3,3,2,1],
    [1,2,3]
) == [1,2,3,3]  # No leftover elements

# No duplicates
assert solution.relativeSortArray(
    [5,4,3,2,1],
    [3,1]
) == [3,1,2,4,5]  # Remaining numbers sorted ascending

# Many duplicates
assert solution.relativeSortArray(
    [2,2,2,1,1,3,3,4],
    [3,2]
) == [3,3,2,2,2,1,1,4]  # Duplicate handling

# Maximum boundary values
assert solution.relativeSortArray(
    [1000,0,500,1000],
    [1000]
) == [1000,1000,0,500]  # Value range boundaries

# arr2 contains all unique values from arr1
assert solution.relativeSortArray(
    [7,8,7,8,9],
    [8,7,9]
) == [8,8,7,7,9]  # Full custom ordering

Test	Why
Example 1	Validates standard mixed ordering case
Example 2	Validates leftover ascending ordering
Single element	Tests minimum constraint size
All elements controlled by arr2	Ensures no leftovers are appended
No duplicates	Validates ascending order for leftovers
Many duplicates	Ensures frequency counting is correct
Maximum boundary values	Verifies handling of 0 and 1000
Full custom ordering	Ensures all elements follow arr2 exactly

Edge Cases

One important edge case occurs when every element in arr1 is already represented in arr2. In this scenario, there are no leftover elements to sort. A buggy implementation might accidentally duplicate values or append unnecessary elements. This implementation avoids that issue by resetting frequencies to 0 after processing each arr2 value, ensuring nothing is re-added later.

Another important case is when arr1 contains many duplicate values, especially duplicates of numbers listed in arr2. Since the problem requires preserving multiplicity, forgetting to count occurrences would produce incorrect results. The frequency array guarantees that every value is added exactly as many times as it originally appeared.

A third edge case involves values at the boundaries of the allowed range, specifically 0 and 1000. Because the algorithm uses array indexing for frequencies, an off-by-one mistake could easily occur. The implementation allocates a frequency array of size 1001 and iterates inclusively from 0 to 1000, ensuring all valid values are handled safely and correctly.