Dutch National Flag (Sort Colors)

Share

Given an array with values 0, 1, and 2, sort them in-place so all 0s come first, then 1s, then 2s. (LeetCode 75: Sort Colors)

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

Solution Approach

Three-pointer approach (Dutch National Flag algorithm by Dijkstra): maintain pointers lo, mid, hi. Invariant: arr[0..lo-1]=0, arr[lo..mid-1]=1, arr[hi+1..n-1]=2.

  • Initialize lo=0, mid=0, hi=n-1.
  • While mid <= hi: if arr[mid]==0 swap arr[lo] and arr[mid], lo++, mid++.
  • If arr[mid]==1, just mid++.
  • If arr[mid]==2, swap arr[mid] and arr[hi], hi-- (do not advance mid).
Java
class Solution {
    public void sortColors(int[] nums) {
        int lo = 0, mid = 0, hi = nums.length - 1;
        while (mid <= hi) {
            if (nums[mid] == 0) {
                int tmp = nums[lo]; nums[lo] = nums[mid]; nums[mid] = tmp;
                lo++; mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int tmp = nums[mid]; nums[mid] = nums[hi]; nums[hi] = tmp;
                hi--;
            }
        }
    }
}
  • Time Complexity: O(N). Single pass
  • Space Complexity: O(1) in-place