Problem 14.5 · Sorting and Divide & ConquerEasy

Relative Sort Array

What it teaches: Counting sort with a custom order: count values, emit them in the given order, then the rest ascending.

Practise it on judges as “Relative Sort Array”.

The problem

Sort arr1 so that elements appearing in arr2 come first, in arr2's order; the remaining elements follow in ascending order. arr2's values are distinct and all appear in arr1.

Example 1

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

Constraints

1 ≤ lengths ≤ 1000
0 ≤ values ≤ 1000

Pattern clues in the wording

→ Small value range
→ A custom order for some values

These clues point to Frequency Counting: Count how many times each value appears (with an int[26] or a HashMap), then answer from the counts.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        return arr1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	arr1 = [2,3,1,3,2,4,6,7,9,2,19] arr2 = [2,1,4,3,9,6]	[2,2,2,1,4,3,3,9,6,7,19]
2	arr1 = [28,6,22,8,44,17] arr2 = [22,28,8,6]	[22,28,8,6,17,44]

From slow to fast

Approaches

1. Optimal: counting sort · O(n + m + range)

Optimal: counting sort

Time O(n + m + range) Space O(range)

count[v] for every value. Write each arr2 value count[v] times (then zero it), then walk v = 0..1000 writing leftovers.

Approach 1

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int v : arr1) count[v]++;
        int k = 0;
        for (int v : arr2) while (count[v]-- > 0) arr1[k++] = v;
        for (int v = 0; v <= 1000; v++) while (count[v]-- > 0) arr1[k++] = v;
        return arr1;
    }
}

Verdict: Linear.

Before you submit

Edge cases and common mistakes

Test these inputs

All of arr1 in arr2
None of the leftovers repeat

Mistakes people make

Forgetting that count[v]-- > 0 leaves count[v] at −1 (harmless here because the loop condition checks > 0).

Interview

Follow-up questions

What if values were up to 10⁹?

Command Palette

The problem

Approaches

Optimal: counting sort

Edge cases and common mistakes

Follow-up questions