Coding · Hashing
Relative Sort Array
- Reported once
- Easy
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You get two integer arrays, arr1 and arr2, where the values of arr2 are distinct and every one of them also appears in arr1. Reorder arr1 so the values named in arr2 come first, following arr2's order with all copies of a value together, and the remaining values follow in ascending order. For arr1 = [5,3,1,3,5,5,8,2] and arr2 = [5,1] the result is [5,5,5,1,2,3,3,8]. Lengths are about a thousand and values are small, but your solution should stay correct for any integers.
Restated in our own words, not a quote from Microsoft or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I ask whether every value of arr2 really appears in arr1 and whether arr2 is distinct. Then I ask about the value range: small non-negative integers allow a counting array, while negatives or huge values need a sort. Can arr1 contain duplicates, which I expect? Should I sort in place or return a new array, and what should happen when arr1 or arr2 is empty?
Assumptions: arr2 is distinct, values are integers of any size, so I do not rely on a small range, I return a new array, an empty arr2 means a plain ascending sort, and leftover values keep all their duplicates in ascending order.
Brute force
Say the obvious answer and why it is too slow.
The quick answer is to sort arr1 with a custom comparator. Look up each value's position in arr2 with indexOf, give values that are not found a position past the end, compare by position, and break ties by the value itself. That is correct, but each comparison does two linear searches, so the cost is O(n log n · m) where m is the length of arr2. Building a position Map first fixes the lookup and gives O(n log n + m), which is fine at a thousand elements. It still sorts everything, including the elements whose order arr2 has already decided, which is more work than needed. Counting avoids comparing those at all: only the leftover values need an actual sort.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n log n · m)
- Time
- O(n + m + r log r)
- Space
- O(n)
The pattern is counting with a hash map. The order inside the arr2 part is dictated by arr2, so it never needs a comparison. All that matters for each such value is how many copies exist. I count every value of arr1 in a Map from value to count. Then I walk arr2 in its own order: for each value I append it as many times as its count, and I delete it from the Map so it cannot be used twice. Whatever remains in the Map is exactly the set of values that arr2 did not mention. I sort those keys ascending and append each one as many times as its count.
Why it is correct: every element of arr1 is placed exactly once, because each value's count is spent either in the arr2 phase or in the leftover phase, never in both. Deleting the key is what guarantees that. The arr2 phase produces arr2 order with copies together by construction. The leftover phase is ascending because of the sort, and copies stay together because I append them in one go.
The cost is one pass to count, one pass over arr2, and a sort of the distinct leftover keys. If r is the number of distinct leftover values, the time is O(n + m + r log r). When the values are known to be small integers, a counting array replaces both the Map and the sort and the time becomes O(n + m + range).
Out loud: I count everything, spend the counts in arr2 order, then sort only what is left over.
Walk it through
A dry run on the example, step by step.
| step | take | copies | output so far | still in map |
|---|---|---|---|---|
| 0 | count all | - | (empty) | 1,2,3,4,6,7,9,19 |
| 1 | 2 | 3 | 2,2,2 | 1,3,4,6,7,9,19 |
| 2 | 1 | 1 | 2,2,2,1 | 3,4,6,7,9,19 |
| 3 | 4 | 1 | 2,2,2,1,4 | 3,6,7,9,19 |
| 4 | 3 | 2 | 2,2,2,1,4,3,3 | 6,7,9,19 |
| 5 | 9 | 1 | 2,2,2,1,4,3,3,9 | 6,7,19 |
| 6 | 6 | 1 | 2,2,2,1,4,3,3,9,6 | 7,19 |
| 7 | sorted rest | 1 each | 2,2,2,1,4,3,3,9,6,7,19 | (empty) |
Use arr1 = [2,3,1,3,2,4,6,7,9,2,19] and arr2 = [2,1,4,3,9,6]. Counting gives three 2s, two 3s, and one each of 1, 4, 6, 7, 9 and 19. The trace shows arr2 being spent in order: three 2s, one 1, one 4, two 3s, one 9 and one 6. After each step the output grows and that value disappears from the Map. What is left at the end is 7 and 19, each with count one. After sorting the keys they are already in order, so the output ends with 7, 19. The final array has eleven entries, the same as arr1, which is a quick sanity check that nothing was lost or duplicated.
The code
Runnable JavaScript, checked against test cases.
function relativeSortArray(arr1, arr2) {
const counts = new Map();
for (const value of arr1) counts.set(value, (counts.get(value) ?? 0) + 1);
const result = [];
for (const value of arr2) {
const copies = counts.get(value) ?? 0;
for (let i = 0; i < copies; i++) result.push(value);
counts.delete(value);
}
const leftovers = [...counts.keys()].sort((a, b) => a - b);
for (const value of leftovers) {
for (let i = 0; i < counts.get(value); i++) result.push(value);
}
return result;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty arr2: the first phase does nothing and the whole array is sorted ascending in the second phase.
- Empty arr1: both phases have nothing to emit, so the result is an empty list.
- Everything named in arr2: the Map is empty after the first phase and the second phase adds nothing.
- Negative values and multi-digit numbers: the sort uses a numeric comparator, so -7 comes before 5 and 9 comes before 10.
- A value in arr2 missing from arr1: this breaks the stated promise, but the lookup falls back to zero copies, so it simply emits nothing.
- Duplicates: counts keep every copy and the copies stay together.
Follow-ups to expect
Where the interviewer pushes next.
- How would you do this in O(n + range) when the values are known to lie between 0 and 1000?
- What if arr2 could contain values that never appear in arr1?
- How would you sort in place without extra arrays, and what would that cost?
- What changes if arr1 is too large to fit in memory?
- How would you make the sort stable for objects that share a key?
Where candidates slip
The mistakes this problem punishes.
- Calling
sort()without a comparator on numbers. It compares as strings, so 10 lands before 9. - Forgetting to delete a value from the Map after the arr2 phase, which makes it appear again among the leftovers.
- Emitting each leftover value only once instead of all its copies.
- Hard-coding a counting array of size 1001, which fails silently on negative or larger values.
- Using
indexOfinside the comparator and not noticing the hidden extra factor of m. - Sorting arr1 in place and surprising the caller who still holds the original order.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.