Sort Colors / Dutch National Flag [Medium] — 3-Pointer Review
Sanjeev SharmaAdvertisement
Problem Statement
Sort array containing only 0, 1, 2 in-place in a single pass.
Input: [2,0,2,1,1,0] → Output: [0,0,1,1,2,2]
Intuition
Dutch National Flag with lo, mid, hi:
[0..lo-1]= 0s,[lo..mid-1]= 1s,[mid..hi]= unsorted,[hi+1..n-1]= 2s
Solutions
C++
void sortColors(vector<int>& nums) {
int lo=0, mid=0, hi=nums.size()-1;
while(mid<=hi){
if(nums[mid]==0) swap(nums[lo++],nums[mid++]);
else if(nums[mid]==2) swap(nums[mid],nums[hi--]);
else mid++;
}
}
Python
def sortColors(nums: list[int]) -> None:
lo = mid = 0
hi = len(nums)-1
while mid <= hi:
if nums[mid] == 0: nums[lo], nums[mid] = nums[mid], nums[lo]; lo+=1; mid+=1
elif nums[mid] == 2: nums[mid], nums[hi] = nums[hi], nums[mid]; hi-=1
else: mid+=1
Complexity
- Time: O(n), Space: O(1)
Advertisement
