Sort array containing 0s, 1s, and 2s in-place.
Input: nums=[2,0,2,1,1,0] → Output: [0,0,1,1,2,2]
Input: nums=[2,0,1] → Output: [0,1,2]
Three-way partition: low pointer for 0s, high pointer for 2s, mid pointer for scanning.
- low=0, mid=0, high=n-1
- While mid <= high
- nums[mid]==0: swap(low,mid), low++, mid++
- nums[mid]==2: swap(mid,high), high-- (don't advance mid)
- nums[mid]==1: mid++
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) { int tmp=nums[low]; nums[low]=nums[mid]; nums[mid]=tmp; low++; mid++; }
else if (nums[mid] == 2) { int tmp=nums[mid]; nums[mid]=nums[high]; nums[high]=tmp; high--; }
else mid++;
}
}
- Time Complexity: O(n)
- Space Complexity: O(1)