Sort Colors
Medium
Given an array nums containing 0, 1, and 2, sort the array in-place so that objects of the same color are adjacent.
The order must be:
0 0 ... 1 1 ... 2 2 ...
You must solve the problem without using a sorting function.
Example 1
Input
n = 6 nums = [2, 0, 2, 1, 1, 0]
Output
[0, 0, 1, 1, 2, 2]
Explanation
The array contains three colors:
- 0 represents red
- 1 represents white
- 2 represents blue
After sorting, all 0s come first, followed by 1s and then 2s.
Example 2
Input
n = 3 nums = [2, 0, 1]
Output
[0, 1, 2]
Explanation
The elements are rearranged in-place into the required order.
Constraints
1 <= n <= 10^5
nums[i] is either 0
1
or 2.
The array must be modified in-place.
Do not use a sorting function.
Hints:
Hint 1
Maintain three regions:
0s | 1s | unknown | 2s
Use three pointers:
low
mid
high
Hint 2
While mid <= high:
- If nums[mid] == 0, swap it with nums[low] and move low and mid.
- If nums[mid] == 1, move mid.
- If nums[mid] == 2, swap it with nums[high] and move high.
Auto
Loading editor...
Input
Expected Output