75. Sort Colors

12 Jul 2025

Reading time ~2 minutes

📌 Algorithm 1: Two Passes of Partitioning

First pass: Push all 0s to the front
Second pass: Push all 2s to the back
After these two passes, all 1s will automatically be placed in the middle.

Solution

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        // First pass: move all 0s to the left side
        while(l <= r){
            // Find the first element from left that's not 0
            while(l <= r && nums[l] == 0) l++;  

            // Find the first element from right that is 0
            while(l <= r && nums[r] >= 1) r--;   

            if(l < r) swap(l, r, nums);
        }
        
        r = nums.length - 1;
        
        while(l <= r){      
            while(l <= r && nums[l] == 1) l++;
            while(l <= r && nums[r] == 2) r--; 
            if(l < r) swap(l, r, nums);
        }
    }

    public void swap(int l, int r, int[] nums){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

Time Complexity: O(N)
Space Complexity: O(1)

📌 Algorithm 2: Dutch National Flag in a Single Pass

This is a classic problem often referred to as the Dutch National Flag problem, originally proposed by Edsger W. Dijkstra.

We maintain three pointers to dynamically partition the array:

low: Tracks the boundary of the 0s region (elements before low are all 0).
cur: The current element being processed (acts as a scanner).
high: Tracks the boundary of the 2s region (elements after high are all 2).

Invariants

At any point, the array is partitioned into four regions:

[0, low): All elements are 0
[low, cur): All elements are 1
(high, n]: All elements are 2

Solution

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, high = nums.length - 1, cur = 0;

        // while unexplored region exists
        while (cur <= high) { 
            if (nums[cur] == 0) {
                swap(cur, low, nums);
                low++; // expand 0s region
                cur++; // since swapped element must be 1 or 0, no need to reprocess
            } else if (nums[cur] == 2) {
                swap(cur, high, nums);
                high--; //expand 2s region

                //since swapped element could be 0, 1, or 2, we must reprocess it
            } else {
                cur++; // nums[cur] == 1
            }
        }
    }

    public void swap(int l, int r, int[] nums){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

Time Complexity: O(N)
Space Complexity: O(1)