Sort Colors (Dutch National Flag Two Pointer)

Problem Statement

Given an array nums with values 0, 1, and 2 (representing colors), sort it in place in a single pass without using a counting/library sort.

Example

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

Two Pointer Approach

The Dutch National Flag algorithm uses three pointers: low (boundary of 0s), mid (scanner), and high (boundary of 2s). Swap 0s to the front, 2s to the back, and leave 1s in the middle.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def sortColors(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] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Java

void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums, low++, mid++);
        else if (nums[mid] == 1) mid++;
        else swap(nums, mid, high--);
    }
}
void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

C++

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] == 1) mid++;
        else swap(nums[mid], nums[high--]);
    }
}

Key Takeaways

• Do not advance mid after swapping with high — the new value is unchecked.
• Three pointers give a one-pass, constant-space three-way partition.
• This generalises to any three-category in-place partition.