Relative Sort Array

Relative Sort Array

What is this problem about?

The Relative Sort Array problem asks you to sort arr1 such that elements appearing in arr2 come first (in arr2's order), followed by remaining elements in ascending order. This easy coding problem uses a custom sort with position map. The array, hash table, sorting, and counting sort interview pattern is demonstrated.

Why is this asked in interviews?

DE Shaw, Meta, Amazon, Google, and Bloomberg ask this to test custom sorting with a priority mapping. Elements with a known priority (in arr2) sort by that priority; unknown elements sort naturally.

Algorithmic pattern used

Priority map + custom sort. Build rank[v] = index of v in arr2. Sort arr1 with comparator: if both have rank, compare by rank. If only one has rank, it comes first. If neither has rank, compare by value.

Python one-liner: sorted(arr1, key=lambda x: (rank.get(x, len(arr2)), x))

Example explanation

arr1=[2,3,1,3,2,4,6,7,9,2,19], arr2=[2,1,4,3,9,6]. rank: {2:0,1:1,4:2,3:3,9:4,6:5}. Sort: 2(0),2(0),2(0),1(1),4(2),3(3),3(3),9(4),6(5), then remaining by value: 7,19. Result: [2,2,2,1,4,3,3,9,6,7,19].

Common mistakes candidates make

• Not putting elements not in arr2 at the end.
• Sorting elements not in arr2 by arr2 order (should be natural ascending).
• Using arr2 position as value instead of as sort key.
• Not handling duplicates in arr1.

Interview preparation tip

Relative Sort Array demonstrates custom sort keys. The tuple key (rank.get(x, len(arr2)+1), x) is elegant: arr2-present elements sort by rank first; absent elements sort by value (all have the same large rank group). This exact pattern appears in "sort by priority then natural order" across many interview problems.