Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sort Colors

MEDIUMProblemSolveExternal Links

Description

You are given an array nums containing n objects, where each object is colored either red, white, or blue. The colors are represented by the integers 0 (red), 1 (white), and 2 (blue).

Your task is to sort the array in-place so that all objects of the same color are grouped together, with the colors appearing in the order: red (0), white (1), blue (2).

You must solve this problem without using any library sort function.

This problem is famously known as the Dutch National Flag problem, originally proposed by Edsger Dijkstra. The challenge is to partition the array into three groups using as few passes and as little extra space as possible.

Examples

Example 1

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

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

Explanation: All 0s (red) are moved to the front, followed by all 1s (white), and then all 2s (blue) at the end. The original array had values interleaved — sorting groups them by color.

Example 2

Input: nums = [2, 0, 1]

Output: [0, 1, 2]

Explanation: Each color appears exactly once. Sorting places them in the natural order: red (0), white (1), blue (2).

Example 3

Input: nums = [0]

Output: [0]

Explanation: A single-element array is already sorted regardless of its value.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 300
  • nums[i] is either 0, 1, or 2

Editorial

Brute Force

Intuition

The most straightforward approach is to use a simple comparison-based sorting algorithm like Bubble Sort. Since the array only contains values 0, 1, and 2, any correct sorting algorithm will naturally group all 0s first, then all 1s, then all 2s.

Think of it like sorting a hand of three types of playing cards (say hearts, diamonds, and spades). Without any clever strategy, you could simply compare adjacent cards and swap them if they're out of order, repeating until no more swaps are needed.

Bubble Sort works by repeatedly walking through the array, comparing each pair of adjacent elements, and swapping them if they're in the wrong order. Each full pass bubbles the largest unsorted element to its correct position at the end.

Step-by-Step Explanation

Let's trace through with nums = [2, 0, 1]:

Pass 1:

Step 1: Compare nums[0]=2 and nums[1]=0. Since 2 > 0, swap. Array becomes [0, 2, 1].

Step 2: Compare nums[1]=2 and nums[2]=1. Since 2 > 1, swap. Array becomes [0, 1, 2].

End of Pass 1. Largest element (2) is now at the end.

Pass 2:

Step 3: Compare nums[0]=0 and nums[1]=1. Since 0 < 1, no swap needed.

End of Pass 2. No swaps occurred, so the array is sorted.

Result: [0, 1, 2]

Bubble Sort — Comparing and Swapping Adjacent Elements — Watch how Bubble Sort compares adjacent elements and swaps them when out of order, gradually bubbling larger values to the right.

Algorithm

  1. For each pass i from 0 to n-2:
    a. Set a flag swapped = false
    b. For each index j from 0 to n-i-2:
    • If nums[j] > nums[j+1], swap them and set swapped = true
      c. If no swaps occurred in this pass, stop early — the array is sorted
  2. The array is now sorted in-place

Code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            bool swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
};
class Solution:
    def sortColors(self, nums: list[int]) -> None:
        n = len(nums)
        for i in range(n - 1):
            swapped = False
            for j in range(n - i - 1):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    swapped = True
            if not swapped:
                break
class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case (array sorted in reverse), Bubble Sort makes n-1 passes, each scanning up to n-1 elements. The total comparisons are approximately n(n-1)/2, which is O(n²). Even with the early-termination optimization, the worst case remains quadratic.

Space Complexity: O(1)

Bubble Sort operates entirely in-place, using only a few temporary variables for swapping and the boolean flag. No additional memory proportional to input size is required.

Why This Approach Is Not Efficient

While Bubble Sort works correctly, it has O(n²) time complexity. Although the constraint n ≤ 300 means O(n²) would technically pass (300² = 90,000 operations), the brute force approach ignores a crucial property: the array only contains three distinct values (0, 1, 2).

A comparison-based sort like Bubble Sort treats the elements generically — it doesn't exploit the fact that there are only three possible values. This is like sorting a deck of cards one-by-one when you know there are only three suits and you could just count how many of each suit you have.

A smarter approach would count the frequency of each value in one pass and then reconstruct the array — reducing time from O(n²) to O(n) with two passes. But can we do even better? The follow-up challenge asks for a single-pass algorithm, which the Dutch National Flag approach achieves.

Better Approach - Counting Sort

Intuition

Since the array contains only three possible values (0, 1, and 2), we can take advantage of this limited range. Instead of comparing elements against each other, we simply count how many 0s, 1s, and 2s exist in the array, and then overwrite the array with the correct number of each value in order.

Imagine you have a bag of red, white, and blue marbles. Instead of sorting them by comparing pairs, you dump them out and count: 3 red, 2 white, 4 blue. Then you line them up: first all 3 red, then 2 white, then 4 blue. You never needed to compare marbles to each other — just count and reconstruct.

This takes two passes through the array: one to count, and one to fill.

Step-by-Step Explanation

Let's trace through with nums = [2, 0, 2, 1, 1, 0]:

Pass 1 — Counting:

Step 1: Initialize counts: count0 = 0, count1 = 0, count2 = 0.

Step 2: Scan nums[0]=2 → increment count2. Counts: {0: 0, 1: 0, 2: 1}.

Step 3: Scan nums[1]=0 → increment count0. Counts: {0: 1, 1: 0, 2: 1}.

Step 4: Scan nums[2]=2 → increment count2. Counts: {0: 1, 1: 0, 2: 2}.

Step 5: Scan nums[3]=1 → increment count1. Counts: {0: 1, 1: 1, 2: 2}.

Step 6: Scan nums[4]=1 → increment count1. Counts: {0: 1, 1: 2, 2: 2}.

Step 7: Scan nums[5]=0 → increment count0. Counts: {0: 2, 1: 2, 2: 2}.

Pass 2 — Filling:

Step 8: Write count0=2 zeros: nums = [0, 0, _, _, _, _].

Step 9: Write count1=2 ones: nums = [0, 0, 1, 1, _, _].

Step 10: Write count2=2 twos: nums = [0, 0, 1, 1, 2, 2].

Result: [0, 0, 1, 1, 2, 2]

Counting Sort — Count Then Fill — Watch how we first count the frequency of each value (0, 1, 2) in one pass, then overwrite the array with the correct number of each value in a second pass.

Algorithm

  1. Initialize three counters: count0 = 0, count1 = 0, count2 = 0
  2. Pass 1 (Count): Traverse the array, incrementing the appropriate counter for each value
  3. Pass 2 (Fill): Overwrite the array:
    a. Fill the first count0 positions with 0
    b. Fill the next count1 positions with 1
    c. Fill the remaining count2 positions with 2

Code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        
        int idx = 0;
        for (int i = 0; i < count0; i++) nums[idx++] = 0;
        for (int i = 0; i < count1; i++) nums[idx++] = 1;
        for (int i = 0; i < count2; i++) nums[idx++] = 2;
    }
};
class Solution:
    def sortColors(self, nums: list[int]) -> None:
        count0 = count1 = count2 = 0
        
        for num in nums:
            if num == 0:
                count0 += 1
            elif num == 1:
                count1 += 1
            else:
                count2 += 1
        
        idx = 0
        for i in range(count0):
            nums[idx] = 0
            idx += 1
        for i in range(count1):
            nums[idx] = 1
            idx += 1
        for i in range(count2):
            nums[idx] = 2
            idx += 1
class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        
        int idx = 0;
        for (int i = 0; i < count0; i++) nums[idx++] = 0;
        for (int i = 0; i < count1; i++) nums[idx++] = 1;
        for (int i = 0; i < count2; i++) nums[idx++] = 2;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array twice — once to count (n operations) and once to fill (n operations). Total: 2n operations, which simplifies to O(n).

Space Complexity: O(1)

We use only three integer counters (count0, count1, count2) and one index variable. This is constant space regardless of input size.

Why This Approach Is Not Efficient

The Counting Sort approach achieves O(n) time, which is asymptotically optimal. However, it has two practical drawbacks:

  1. Two passes required: It traverses the array twice — once for counting and once for filling. The follow-up question specifically asks: can we do this in a single pass?

  2. Not stable and destructive: The counting approach overwrites the original array values. If the 0s, 1s, and 2s represented keys of objects (e.g., colored balls with names on them), we'd lose the original objects because we're replacing values rather than rearranging them.

The key insight for doing better is that with exactly three distinct values, we can use three pointers to partition the array into three regions in a single scan. This is the Dutch National Flag algorithm, which achieves O(n) time in just one pass while performing swaps instead of overwrites — preserving the original elements.

Optimal Approach - Dutch National Flag Algorithm

Intuition

The Dutch National Flag algorithm (invented by Edsger Dijkstra) partitions an array of three distinct values into three contiguous groups using just one pass and constant space.

The idea is to maintain three pointers that divide the array into four regions:

  • [0 .. lo-1] → All 0s (confirmed red zone)
  • [lo .. mid-1] → All 1s (confirmed white zone)
  • [mid .. hi] → Unprocessed elements (unknown zone)
  • [hi+1 .. n-1] → All 2s (confirmed blue zone)

We process the unknown zone by examining the element at mid:

  • If it's 0: swap it with the element at lo, then advance both lo and mid (we know what came from the 1s zone is a 1)
  • If it's 1: it's already in the right zone, just advance mid
  • If it's 2: swap it with the element at hi, then shrink hi (do NOT advance mid because the swapped element hasn't been examined yet)

Think of it like a traffic officer directing cars into three lanes. The officer (mid pointer) inspects each car: red cars go left (swap to lo), white cars stay in the middle, and blue cars go right (swap to hi). The officer processes each car exactly once.

Step-by-Step Explanation

Let's trace through with nums = [2, 0, 2, 1, 1, 0]:

Step 1: Initialize lo=0, mid=0, hi=5. Entire array is the unknown zone.

Step 2: Examine nums[mid]=nums[0]=2. It's a 2, so swap nums[mid] with nums[hi]. Swap positions 0 and 5: array becomes [0, 0, 2, 1, 1, 2]. Decrement hi to 4. Do NOT increment mid (the swapped-in value at mid=0 needs to be checked).

Step 3: Examine nums[mid]=nums[0]=0. It's a 0, so swap nums[mid] with nums[lo]. Both are index 0, so it's a self-swap (no change). Increment both lo to 1 and mid to 1. Array: [0, 0, 2, 1, 1, 2].

Step 4: Examine nums[mid]=nums[1]=0. It's a 0, so swap nums[mid]=nums[1] with nums[lo]=nums[1]. Self-swap again. Increment lo to 2, mid to 2. Array: [0, 0, 2, 1, 1, 2].

Step 5: Examine nums[mid]=nums[2]=2. It's a 2, so swap nums[2] with nums[hi]=nums[4]. Array becomes [0, 0, 1, 1, 2, 2]. Decrement hi to 3. Do NOT increment mid.

Step 6: Examine nums[mid]=nums[2]=1. It's a 1, so just increment mid to 3. Array unchanged: [0, 0, 1, 1, 2, 2].

Step 7: Examine nums[mid]=nums[3]=1. It's a 1, so increment mid to 4. Array unchanged: [0, 0, 1, 1, 2, 2].

Step 8: Now mid=4 > hi=3, so we stop. The array is fully sorted.

Result: [0, 0, 1, 1, 2, 2]

Dutch National Flag — Three-Pointer Single-Pass Partition — Watch how three pointers (lo, mid, hi) partition the array into three zones in a single pass. The mid pointer examines each element and directs it to the correct zone via swaps.

Algorithm

  1. Initialize three pointers: lo = 0, mid = 0, hi = n - 1
  2. While mid ≤ hi:
    • If nums[mid] == 0:
      • Swap nums[lo] and nums[mid]
      • Increment both lo and mid
    • Else if nums[mid] == 1:
      • Increment mid (element is already in the correct zone)
    • Else (nums[mid] == 2):
      • Swap nums[mid] and nums[hi]
      • Decrement hi (do NOT increment mid — the swapped-in element needs inspection)
  3. The array is now sorted in-place with all 0s, then 1s, then 2s

Code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int lo = 0, mid = 0, hi = nums.size() - 1;
        
        while (mid <= hi) {
            if (nums[mid] == 0) {
                swap(nums[lo], nums[mid]);
                lo++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[hi]);
                hi--;
            }
        }
    }
};
class Solution:
    def sortColors(self, nums: list[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1
        
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1
class Solution {
    public void sortColors(int[] nums) {
        int lo = 0, mid = 0, hi = nums.length - 1;
        
        while (mid <= hi) {
            if (nums[mid] == 0) {
                int temp = nums[lo];
                nums[lo] = nums[mid];
                nums[mid] = temp;
                lo++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int temp = nums[mid];
                nums[mid] = nums[hi];
                nums[hi] = temp;
                hi--;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Each iteration of the while loop either advances mid forward or moves hi backward (or both). Since mid starts at 0 and can only increase, and hi starts at n-1 and can only decrease, the loop runs at most n times total. Each iteration does O(1) work (one comparison and at most one swap). Therefore, total time is O(n) — and crucially, this is achieved in a single pass.

Space Complexity: O(1)

We use only three integer pointers (lo, mid, hi) and one temporary variable for swapping. No additional memory that grows with input size. This is truly constant space.