Problem
Given an array with values 0, 1, and 2 representing colors, sort them in-place in one pass.
Example
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]Solution
Three pointers. low for next 0, high for next 2, mid scans. Swap based on value at mid.
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 2:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
else:
mid += 1function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++; mid++;
} else if (nums[mid] === 2) {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
} else mid++;
}
}void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) swap(nums[low++], nums[mid++]);
else if (nums[mid] == 2) swap(nums[mid], nums[high--]);
else mid++;
}
}public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) { int t = nums[low]; nums[low++] = nums[mid]; nums[mid++] = t; }
else if (nums[mid] == 2) { int t = nums[mid]; nums[mid] = nums[high]; nums[high--] = t; }
else mid++;
}
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
When swapping with low, mid moves too (low’s old value was 1, now correctly placed). When swapping with high, mid stays (we haven’t inspected the new value yet).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?