Sort Colors
Medium · Two Pointers · Array · Two Pointers · Sorting
Problem
nums holds only the values 0, 1 and 2 — think of them as red, white and blue. Rearrange it in place so that all the 0s come first, then all the 1s, then all the 2s. The tests read nums after your call; the return value is ignored.
Do not call a library sort. Counting the three values and writing them back works; the real target is one pass with O(1) extra space, which needs a pointer for each boundary.
LeetCode stops at 300 values. The tests here go up to 30,000, so that a quadratic sort shows up as slow.
Examples
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Two of each colour, now grouped in order.
Input: nums = [2,0,1] Output: [0,1,2]
The 2 goes to the back and the 0 to the front.
Constraints
- 1 <= len(nums) <= 3 * 10^4 (LeetCode: 300)
- nums[i] is 0, 1 or 2
- sort in place, without a library sort
Approaches
- Insertion sort — time O(n²), space O(1)
Follow-up
Can you sort nums in a single pass using only O(1) extra space?
Related problems
Start free on Cariara · Coding problems · System design studio
