Course4all
Join us on telegram
Home/dsa/Two Pointers/Sort Colors

Sort Colors

Master this topic with zero to advance depth.

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue. We use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Visual Representation

Array: [2, 0, 2, 1, 1, 0] Step 1: Move 0s to the front (Left side). Step 2: Move 2s to the end (Right side). Step 3: 1s will naturally be in the middle. Result: [0, 0, 1, 1, 2, 2]
Medium

Examples

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

The array is sorted in-place to group 0s, 1s, and 2s.

Approach 1

Level I: Two Pass (Counting)

Intuition

Since there are only three possible values (0, 1, 2), we can count the frequency of each and then overwrite the original array.

⏱ O(N)💾 O(1)

Detailed Dry Run

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

  1. Count: 0: 2, 1: 2, 2: 2.
  2. Overwrite: nums[0..1]=0, nums[2..3]=1, nums[4..5]=2. Result: [0, 0, 1, 1, 2, 2]
java
public class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int n : nums) count[n]++;
        int idx = 0;
        for (int i = 0; i < 3; i++) {
            while (count[i]-- > 0) nums[idx++] = i;
        }
    }
}

⚠️ Common Pitfalls & Tips

Requires two passes over the data.

Approach 2

Level II: Better (Two Pass - Two Pointers)

Intuition

Instead of counting all colors at once, we can use two passes with two pointers. In the first pass, we move all 0s to the front. In the second pass, we move all 1s from where the 0s ended.

  1. Pass 1: Pointer p at start. Iterate, if nums[i] == 0, swap with p++.
  2. Pass 2: Iterate starting from p. If nums[i] == 1, swap with p++.
⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2, 0, 1]

  1. Pass 1 (for 0): [0, 2, 1], p=1.
  2. Pass 2 (for 1): [0, 1, 2], p=2.
java
public void sortColors(int[] nums) {
    int p = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) swap(nums, i, p++);
    }
    for (int i = p; i < nums.length; i++) {
        if (nums[i] == 1) swap(nums, i, p++);
    }
}
private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }

⚠️ Common Pitfalls & Tips

Still O(N) but takes two passes. Standard Dutch National Flag is better.

Approach 3

Level III: Optimal (One Pass - Dutch National Flag)

Intuition

Use three pointers to partition the array: low for 0s, high for 2s, and curr for the current element. This allows sorting in a single pass.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2,0,1]

  1. low=0, curr=0, high=2. nums[0]=2: Swap with high. Array: [1,0,2], high=1.
  2. curr=0. nums[0]=1: curr++. Array: [1,0,2], curr=1.
  3. curr=1. nums[1]=0: Swap with low. Array: [0,1,2], low=1, curr=2.
  4. DONE.
java
public void sortColors(int[] nums) {
    int low = 0, curr = 0, high = nums.length - 1;
    while (curr <= high) {
        if (nums[curr] == 0) {
            int tmp = nums[low];
            nums[low++] = nums[curr];
            nums[curr++] = tmp;
        } else if (nums[curr] == 2) {
            int tmp = nums[high];
            nums[high--] = nums[curr];
            nums[curr] = tmp;
        } else curr++;
    }
}

⚠️ Common Pitfalls & Tips

Be careful not to increment curr when swapping with high, as the newly swapped element needs to be checked.

← Previous Question4Sum
Next Question →Valid Palindrome II