Shelf Order From a Reference
Problem
A shop restocks its shelf by product id. The manager has a preferred order reference (distinct ids). Every item in items whose id appears in reference must be placed following that order, repeats kept together.
Items whose id is not in reference go at the end, in ascending id order. Return the arranged items.
Example 1
- Input:
- items = [4, 9, 2, 4, 7, 3, 9], reference = [9, 4, 2]
- Output:
- [9, 9, 4, 4, 2, 3, 7]
First every 9, then every 4, then the 2; the leftovers 3 and 7 follow in ascending order.
Example 2
- Input:
- items = [5, 1], reference = [8]
- Output:
- [1, 5]
Constraints
- 0 ≤ items.length ≤ 10^5
- 0 ≤ reference.length ≤ 10^4, all values in reference are distinct
- -10^9 ≤ items[i], reference[j] ≤ 10^9
Hint
Show the first hint
Think of the reference as defining a rank for some ids.
Walkthrough
How to approach it
01Clarify before coding
- Can reference contain ids that never appear in items? Yes, they contribute nothing.
- Are ids in reference distinct? Yes, so each one has a single rank.
- How are leftovers ordered? Ascending by id.
02Brute force
For each reference id, scan the whole items array and copy matches; then collect the rest and sort them.
Cost: O(n·m + n log n) for n items and m reference ids: up to 10^9 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.