sorting · Problem 1 of 1
Sort Colors
nums contains only 0, 1 and 2. Return it sorted.
sortColors([2, 0, 2, 1, 1, 0]) -> [0, 0, 1, 1, 2, 2]
A comparison sort does this in O(n log n) and calling one is a perfectly good answer to give first. But three known values is extra information, and the point of the problem is what that information buys: one pass, no comparisons between elements.
Counting each value and rewriting the array is the two-pass version. The single-pass one is the Dutch national flag partition.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| sortColors([2,0,2,1,1,0]) | a mixed array | [0,0,1,1,2,2] | — |
| sortColors([0,1,2]) | already sorted | [0,1,2] | — |
| sortColors([2,1,0]) | exactly reversed | [0,1,2] | — |
| sortColors([1,1,1]) | one value only | [1,1,1] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(n)
One pass, and in place if you are allowed to mutate the input — the copy here exists so the tests compare a returned value. Beating O(n log n) is only possible because the set of values is known in advance; on arbitrary input no comparison sort can do better.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left