Three-Bin Sort
MediumTwo Pointers
Problem
A parcel sorter labels every package with a priority: 0 (express), 1 (standard) or 2 (economy). Given the array codes, reorder it in place so that all 0s come first, then all 1s, then all 2s.
Do it in a single pass with O(1) extra memory, without calling a library sort and without counting first.
Example 1
- Input:
- codes = [2, 0, 1, 2, 0, 1]
- Output:
- [0, 0, 1, 1, 2, 2]
Example 2
- Input:
- codes = [1, 0]
- Output:
- [0, 1]
Constraints
- 1 ≤ codes.length ≤ 10^5
- codes[i] is 0, 1 or 2
Hint
Show the first hint
Picture three zones growing at the same time: 0s on the left, 2s on the right, 1s in the middle.
Walkthrough
How to approach it
01Clarify before coding
- Are values guaranteed to be only 0, 1, 2? Yes.
- Is counting then rewriting allowed? It works in two passes, but this task asks for one pass.
- Must it be in place? Yes, the function returns nothing.
02Brute force
Count the 0s, 1s and 2s, then overwrite the array; or use a general sort.
Cost: Counting is O(n) but needs two passes; a comparison sort is O(n log n).
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.