12. Sort Colors
Rearrange the input so every 0 comes before every 1, and every 1 comes before every 2. The task concerns these three categories and must be completed without calling a comparison-based sort.
Keep the same array object and retain every occurrence. Values outside the permitted categories are covered by the precise input contract below.
Example 1
Input
[2,0,2,1,1,0]
Output
[0,0,1,1,2,2]
Explanation: Every occurrence is partitioned by its bounded key.
Example 2
Input
[2,0,1]
Output
[0,1,2]
Explanation: A swap from the high end can bring an unknown value into mid.
Constraints
0 <= nums.length <= 105nums[i] is 0, 1 or 2
Hints
Hint 1
Separate the processed values from an unknown interval.
Hint 2
Which swap brings a known value back, and which brings an unknown one?
Hint 3
Use low/mid/high and recheck mid after swapping with high.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Unknown values swapped in from high
[2,0,2,1,1,0]
[0,0,1,1,2,2]