Skip to main content

Sort Colors

— Prerna Sharma

Sort Colors

Sort Colors – LeetCode #75 | DSA for Beginners

Brute force sort → counting sort → Dutch National Flag one-pass algorithm. Three pointers, zero extra space.

Medium Two Pointers Array Sorting

Problem Statement

Given

An array nums with n objects coloured red, white, or blue, represented by integers 0, 1, and 2 respectively. Sort them in-place so that objects of the same colour are adjacent, in the order 0 → 1 → 2. You cannot use a library sort function.

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]

Constraints: 1 ≤ n ≤ 300  •  nums[i] ∈ {0, 1, 2}
Follow-up: Can you solve it in one pass using only constant extra space?

Why Is It Called the Dutch National Flag? 🇳🇱

This problem was formulated by computer scientist Edsger W. Dijkstra. The Dutch national flag has three horizontal bands — red, white, and blue — exactly like our three values 0, 1, 2. Dijkstra’s challenge: partition any sequence of red, white, and blue elements into those three groups in a single pass.

Goal: transform any ordering into this:

0
red
0
red
1
white
1
white
2
blue
2
blue
0s zone
1s zone
2s zone

Three Approaches — Building up to Optimal

🐌 Approach 1
Built-in Sort

Call the language’s sort. Works, but O(n log n) and violates the spirit of the problem.

O(n log n) O(1)

📊 Approach 2
Counting Sort

Count 0s, 1s, 2s in one pass. Overwrite the array in a second pass. Two passes, O(n).

O(n) — 2 pass O(1)

⚡ Approach 3
Dutch National Flag

Three pointers, one pass, in-place. Constant space. The interview answer.

O(n) — 1 pass O(1)

Approach 1 — Built-in Sort

The naive idea: just sort the array. Since values are 0, 1, 2 any comparison sort works. This violates the follow-up constraint and misses the educational point entirely, but it’s worth mentioning as a baseline.



  
  
Approach 2 — Counting Sort (Two Pass)

  
Since there are only three distinct values, we can count each one, then overwrite the array. Simple, but requires two passes over the data.


  
    
    
  • Pass 1: iterate through nums and count how many 0s, 1s, and 2s exist.
    • 
    
  • Pass 2: overwrite nums — write count0 zeros, then count1 ones, then count2 twos.
    • 
    
  • Return. (No extra data structure needed beyond three counters.)
    • 
  


  


  
🔍 Dry Run — Counting Sort

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

  

    
PassActionState

    
      
Pass 1Count valuescount0=2, count1=2, count2=2

      
Pass 2aWrite 2 zeros[0, 0, _, _, _, _]

      
Pass 2bWrite 2 ones[0, 0, 1, 1, _, _]

      
Pass 2cWrite 2 twos[0, 0, 1, 1, 2, 2] ✅

    
  


  

    ⚠️ The limitation: Two passes means reading the array twice. For streaming data or memory-mapped files this matters. And the follow-up explicitly asks for one pass. Time to upgrade to the Dutch National Flag algorithm.
  


  
  
Approach 3 — Dutch National Flag (Optimal) ⚡


  
The Three-Pointer Idea

  
We maintain three pointers that divide the array into four live regions at all times:


  

    

      
0..left−1

      
All confirmed 0s (reds)

    

    

      
left..mid−1

      
All confirmed 1s (whites)

    

    

      
mid..right

      
Unknown — not yet classified

    

    

      
right+1..n−1

      
All confirmed 2s (blues)

    

  


  
We always inspect nums[mid] (the first unknown element) and take one of three actions:


  

    
nums[mid] valueActionWhy

    
      

        0 (red)
        swap(mid, left) • left++ • mid++
        Belongs in red zone. After swap, left points at a 1 we’ve already seen, so mid can safely advance.
      

      

        1 (white)
        mid++
        Already in the right zone. Just expand white region rightward.
      

      

        2 (blue)
        swap(mid, right) • right--
        Belongs in blue zone. After swap, the new nums[mid] is unknown — do NOT advance mid.
      

    
  


  

    
❓ Why doesn’t mid advance when we swap a 2?

    
When we swap nums[mid] with nums[right], the value that comes to mid from the right side has never been examined before — it could be 0, 1, or 2. We must inspect it before moving on. When we swap a 0 with nums[left], the value at left must be a 1 (we’ve already classified everything before mid), so we can safely advance both pointers.

  


  
  
🔍 Dry Run — Dutch National Flag

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

  
Initial: left=0, mid=0, right=5


  

    
0 (red)

    
1 (white)

    
2 (blue)

    

    
left ptr

    
mid ptr

    
right ptr

  


  
  

    

      Step 1 — nums[mid]=2 → swap with right
    

    

      
2
0
L,M

      
0
1

      
2
2

      
1
3

      
1
4

      
0
5
R

    

    

      After swap(0,5) & right--:
    

    

      
0
0
L,M

      
0
1

      
2
2

      
1
3

      
1
4
R

      
2
5
✓done

    

    
nums[mid]=2 → swap(mid=0, right=5) → right-- → right=4 • mid stays at 0 (new value unknown)

  


  
  

    

      Step 2 — nums[mid]=0 → swap with left
    

    

      
0
0
L,M

      
0
1

      
2
2

      
1
3

      
1
4
R

      
2
5

    

    

      swap(0,0) is no-op. left++ & mid++:
    

    

      
0
0
✓

      
0
1
L,M

      
2
2

      
1
3

      
1
4
R

      
2
5

    

    
nums[mid]=0 → swap(mid=0, left=0) → left=1, mid=1

  


  
  

    

      Step 3 — nums[mid]=0 → swap with left
    

    

      
0
0
✓

      
0
1
L,M

      
2
2

      
1
3

      
1
4
R

      
2
5

    

    

      swap(1,1) is no-op. left++ & mid++:
    

    

      
0
0
✓

      
0
1
✓

      
2
2
L,M

      
1
3

      
1
4
R

      
2
5

    

    
nums[mid]=0 → swap(mid=1, left=1) → left=2, mid=2

  


  
  

    

      Step 4 — nums[mid]=2 → swap with right
    

    

      
0
0

      
0
1

      
2
2
L,M

      
1
3

      
1
4
R

      
2
5

    

    

      swap(2,4) & right--:
    

    

      
0
0

      
0
1

      
1
2
L,M

      
1
3
R

      
2
4
✓

      
2
5
✓

    

    
nums[mid]=2 → swap(mid=2, right=4) → right-- → right=3 • mid stays at 2

  


  
  

    

      Step 5 — nums[mid]=1 → just advance mid
    

    

      
0
0

      
0
1

      
1
2
L,M

      
1
3
R

      
2
4

      
2
5

    

    

      mid++:
    

    

      
0
0

      
0
1

      
1
2
L

      
1
3
M,R

      
2
4

      
2
5

    

    
nums[mid]=1 → mid++ → mid=3. left stays at 2.

  


  
  

    

      Step 6 — nums[mid]=1 → just advance mid
    

    

      
0
0

      
0
1

      
1
2
L

      
1
3
M,R

      
2
4

      
2
5

    

    

      mid++ → mid=4 > right=3 → loop ends:
    

    

      
0
0
✓

      
0
1
✓

      
1
2
✓

      
1
3
✓

      
2
4
✓

      
2
5
✓

    

    
mid=4 > right=3 → while loop exits • Result: [0, 0, 1, 1, 2, 2] ✅

  


  

    6 steps total for n=6. Each element is touched at most twice (once by mid, once by left or right). The loop terminates when mid > right — no unknown region remains.
  


  
  
Time & Space Complexity

  

    
ApproachTimeSpacePassesNote

    
      
Built-in SortO(n log n)O(1)1Violates problem spirit

      
Counting SortO(n)O(1)2Simple but two sweeps

      
Dutch National FlagO(n)O(1)1Interview gold standard

    
  


  

    Key Insight: The while (mid ≤ right) loop processes each element exactly once. When we encounter a 2 and swap, we don’t advance mid because we’ve never seen the incoming value. When we encounter a 0 and swap, the incoming value at left must already be a 1 (everything left of mid is classified), so advancing both is safe. This asymmetry is the core of the algorithm.
  


  
  
Code — All Approaches × All Languages


  
  

    

      Approach 1
      🐌 Built-in Sort
      
        O(n log n)
        O(1) space
      
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 2
      📊 Counting Sort — Two Pass
      
        O(n)
        O(1) space
      
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 3
      ⚡ Dutch National Flag — One Pass (Optimal)
      
        O(n)
        O(1) space
      
    

    

      💡 Three pointers: left = boundary of 0s  |  mid = current element  |  right = boundary of 2s

      Loop invariant: everything before left is 0, between left and mid is 1, after right is 2.
    

    

      
      
      
      
    

    

    

    

    

  


  

  

    🎯 Interview Tip: Always mention all three approaches and their trade-offs. Start with "I can use built-in sort in O(n log n) but since there are only 3 distinct values, counting sort gives O(n) in two passes." Then land the Dutch National Flag as the optimal one-pass solution. Interviewers love seeing you know why mid doesn’t advance when swapping a 2 — explain the loop invariant. This pattern appears in 3-way partition quicksort and Partition Array by Odd and Even.