Introduction

The Sort Colors problem involves sorting an array containing only:

 0s, 1s, and 2s

where:

  • 0 represents Red
  • 1 represents White
  • 2 represents Blue

The task is to:

  • sort the array in-place
    without using built-in sorting

This problem is one of the most important applications of:

 Dutch National Flag Algorithm

This problem helps in understanding:

  • partitioning techniques
  • two pointers
  • three pointers
  • in-place sorting

Example

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

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

Explanation:
All 0s come first,
then 1s,
then 2s.

Constraints

1 <= arr.length <= 10^5arr[i] is either:
0, 1, or 2

Approach 1 : Counting Method

Explanation

The simplest way to solve this problem is:

  1. Count:
    • number of 0s
    • number of 1s
    • number of 2s
  2. Rewrite array using counts

This works efficiently because:

  • only three unique values exist

Steps

  1. Count frequencies.
  2. Fill array with 0s.
  3. Fill array with 1s.
  4. Fill array with 2s.
  5. Return sorted array.

Dry Run

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

Count values:
0 → 2 times
1 → 2 times
2 → 2 times

Rebuild array:
[0, 0, 1, 1, 2, 2]

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

Counting Method Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Array is traversed twice.

Space Complexity: O(1)
Explanation:
Only counters are used.
Approach 2 : Dutch National Flag Algorithm

Explanation

The optimized solution uses:

 Three Pointers

Pointers:

  • low
  • mid
  • high

Rules:

  • 0 goes left
  • 1 stays middle
  • 2 goes right

This sorts array in a single traversal.

Steps

  1. Initialize:
    • low = 0
    • mid = 0
    • high = n - 1
  2. Traverse while mid <= high.
  3. If value is 0:
    • swap with low
  4. If value is 1:
    • move mid
  5. If value is 2:
    • swap with high

Dry Run

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

Initial:
low = 0
mid = 0
high = 5
arr[mid] = 2
Swap with high

Array:
[0, 0, 2, 1, 1, 2]
high--
arr[mid] = 0
Swap with low

Array:
[0, 0, 2, 1, 1, 2]
low++
mid++

Continue traversal...

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

Dutch National Flag Algorithm Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Array is traversed only once.

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Edge Cases

  1. Empty array
  2. All values same
  3. Already sorted array
  4. Reverse sorted array
  5. Only two unique values present

Why This Problem is Important

Sort Colors helps in understanding:

  1. Partitioning techniques
  2. Three pointer approach
  3. In-place sorting
  4. Dutch National Flag Algorithm
  5. Efficient traversal

It is one of the most important partitioning interview problems.

Real-World Applications

Partitioning concepts are used in:

  1. Quick Sort
  2. Data segregation
  3. Memory optimization
  4. Stream processing
  5. Task scheduling systems

Common Mistakes

  1. Incorrect pointer movement
  2. Swapping with wrong index
  3. Incrementing mid incorrectly
  4. Wrong loop condition

Interview Tips

Interviewers often expect:

  1. Dutch National Flag explanation
  2. O(n) in-place optimization
  3. Three pointer understanding

Always explain:

  • role of low pointer
  • role of mid pointer
  • role of high pointer

Related Questions

  1. Partition Array
  2. Quick Sort
  3. Move Zeroes
  4. Sort Array By Parity
  5. Kth Largest Element

Final Takeaway

The Sort Colors problem is a fundamental partitioning problem that teaches the Dutch National Flag Algorithm and efficient in-place sorting techniques. Understanding this problem builds a strong foundation for advanced partitioning and sorting interview problems.