Dutch National Flag (Sort Colors)

Share

Sort array containing 0s, 1s, and 2s in-place.

Example 1
Input: nums=[2,0,2,1,1,0] → Output: [0,0,1,1,2,2]
Example 2
Input: nums=[2,0,1] → Output: [0,1,2]

Solution Approach

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++
Java
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)