138. Three-Flag Sort
A signal tower flies a row of flags, each coloured red, white or blue. The colours are stored in the array colours as the numbers 0 for red, 1 for white and 2 for blue, in no particular order.
Rearrange colours in place so that all the red flags come first, followed by all the white flags, followed by all the blue flags. The method returns nothing: the array itself must hold the sorted flags when it finishes. Do not call a library sort and do not count the colours first; a single pass over the array that swaps flags into place is enough, using only a constant amount of extra memory.
Example 1
- Input:
- colours = [2,0,1,2,0,1]
- Output:
- [0,0,1,1,2,2]
- Explanation:
The array holds two reds, two whites and two blues, so after sorting it is [0,0,1,1,2,2].
Example 2
- Input:
- colours = [1,2,1,1]
- Output:
- [1,1,1,2]
- Explanation:
No red flags exist: the white flags move to the front, giving [1,1,1,2].
Example 3
- Input:
- colours = [2]
- Output:
- [2]
- Explanation:
A single flag is already in place.
Constraints
1 ≤ colours.length ≤ 2000
colours[i] is 0, 1 or 2
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
coloursafter your method returns. - Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)