75. Sort Colors

Time: O(n)

Space: O(1)

Intuition

Three-way partition using Dijkstra's Dutch National Flag algorithm: maintain three regions - [0, low-1] all 0s, [low, mid-1] all 1s, [high+1, n-1] all 2s - expanding them via swaps.

Algorithm

1Initialise low=0, mid=0, high=n-1.
2While mid <= high:
3 if nums[mid]==0: swap(mid, low), low++, mid++.
4 if nums[mid]==1: mid++ (already in correct region).
5 if nums[mid]==2: swap(mid, high), high-- (do NOT increment mid - new nums[mid] is unknown).

Example Walkthrough

Input: [2,0,2,1,1,0]

1.mid=0(2): swap(0,5)->[0,0,2,1,1,2], high=4.
2.mid=0(0): swap(0,0)->same, low=1,mid=1.
3.mid=1(0): swap(1,1), low=2,mid=2.
4.mid=2(2): swap(2,4)->[0,0,1,1,2,2], high=3.
5.mid=2(1): mid=3. mid=3(1): mid=4. 4>3=high, stop.

Output: [0,0,1,1,2,2]

Common Pitfalls

•When swapping with high, do NOT increment mid - the swapped element from high could be 0, 1, or 2 and needs to be re-examined.

75.cs

// Approach: Dutch National Flag algorithm — single-pass three-way partition.
// Maintain three pointers: low (next position for 0), mid (current element), high (next position for 2).
// If nums[mid] == 0: swap with nums[low], advance both low and mid.
// If nums[mid] == 2: swap with nums[high], retreat high only (mid stays to re-examine the swapped value).
// If nums[mid] == 1: just advance mid.
// Loop ends when mid > high; the array is now sorted with 0s, 1s, and 2s in place.
// Time: O(n) Space: O(1) — no counting sort, true single pass.

public class Solution
{
    public void SortColors(int[] nums)
    {
        int l = 0;               // The next 0 should be placed in l.
        int r = nums.Length - 1; // The next 2 should be placed in r.

        for (int i = 0; i <= r;)
        {
            if (nums[i] == 0)
                Swap(nums, i++, l++);
            else if (nums[i] == 1)
                ++i;
            else
            {
                // We may swap a 0 to index i, but we're still not sure whether this 0
                // is placed in the correct index, so we can't move pointer i.
                Swap(nums, i, r--);
            }
        }
    }

    private void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Was this solution helpful?