Sort Colors

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

You are given nums with values only in {0,1,2}. Reorder it in place so all 0s come first, then 1s, then 2s.

Avoid built-in sorting because the interview intent is one-pass pointer partitioning.

Examples

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

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

🎯 Real-World Analogy

Three-Lane Event Check-In

Guests must be routed into Bronze (0), Silver (1), and Gold (2) lanes. One staff member scans each arriving guest while two boundary markers track where Bronze ends and where Gold starts.

Bronze guests swap left, Gold guests swap right, and Silver guests stay in the middle. The middle lane forms automatically.

💡 Key Insights

Maintain three regions: [0..low-1]=0, [low..mid-1]=1, [high+1..end]=2.
mid scans unknown region [mid..high].
If nums[mid]==0, swap with low, then increment both.
If nums[mid]==2, swap with high, decrement high only.

💻 Solution Approaches

Approach 1: Counting Sort (Two Passes)

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

Count zeros, ones, twos, then overwrite array. Works well but does not teach in-place partitioning.

Approach 2: Dutch National Flag (Recommended)

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

Python Implementation

          from typing import List


def sort_colors(nums: List[int]) -> None:
    low = 0
    mid = 0
    high = 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
        

JavaScript Implementation

          function sortColors(nums) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low += 1;
      mid += 1;
    } else if (nums[mid] === 1) {
      mid += 1;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high -= 1;
    }
  }
}
        

🔍 Step-by-Step Walkthrough

Trace [2,0,2,1,1,0]:

Start: low=0, mid=0, high=5
mid=0 sees 2 -> swap with high -> [0,0,2,1,1,2], high=4
mid=0 sees 0 -> swap low/mid, low=1, mid=1
mid=1 sees 0 -> swap low/mid, low=2, mid=2
mid=2 sees 2 -> swap with high -> [0,0,1,1,2,2], high=3
mid=2..3 sees 1s -> mid advances -> done

⚡ Complexity Analysis

Time: O(N) because each element is moved into the correct partition at most once or twice under pointer control.

Space: O(1) because partitioning uses only three indices.

🔧 Edge Cases

All same color: [0,0,0] or [2,2].
Already sorted: [0,0,1,1,2,2].
Reverse grouped: [2,2,1,1,0,0].
Small arrays: length 1 and 2.

🧪 Test Cases

Python

def test_sort_colors():
    data = [2, 0, 2, 1, 1, 0]
    sort_colors(data)
    assert data == [0, 0, 1, 1, 2, 2]

    data = [2, 0, 1]
    sort_colors(data)
    assert data == [0, 1, 2]

    data = [1, 0, 2, 0, 1, 2]
    sort_colors(data)
    assert data == [0, 0, 1, 1, 2, 2]

    print("all tests passed")

JavaScript

function testSortColors() {
  const a = [2, 0, 2, 1, 1, 0];
  sortColors(a);
  console.assert(JSON.stringify(a) === JSON.stringify([0, 0, 1, 1, 2, 2]), "test 1");

  const b = [2, 0, 1];
  sortColors(b);
  console.assert(JSON.stringify(b) === JSON.stringify([0, 1, 2]), "test 2");

  const c = [1, 0, 2, 0, 1, 2];
  sortColors(c);
  console.assert(JSON.stringify(c) === JSON.stringify([0, 0, 1, 1, 2, 2]), "test 3");

  console.log("all tests passed");
}

💼 Interview Tips

Name the partition invariants early to show control.
Explain why mid does not advance after swapping with high.
Compare DNF with counting sort and justify tradeoff.
Walk through one array with pointer movements.

🎓 Key Takeaways

Dutch National Flag gives one-pass in-place sorting for 3 values.
Pointer invariants are the core correctness proof.
Understanding when not to move mid is the main interview trap.

← Back to All Algorithms