Introduction

The Sort 0s, 1s, and 2s problem involves sorting an array containing only:

  • 0s
  • 1s
  • 2s

Given an array arr[], the task is to sort the array in ascending order without using built-in sorting methods.

This problem introduces the famous:

 Dutch National Flag Algorithm

This problem helps in understanding:

  • partitioning techniques
  • pointer manipulation
  • in-place sorting
  • efficient traversal strategies

Example

Input: arr[] = [2,0,2,1,1,0]Output: [0,0,1,1,2,2]
Explanation:
After sorting:
0s come first
1s come next
2s come last

Input: arr[] = [2,1,0,1,2,0]
Output: [0,0,1,1,2,2]
Explanation:
Array is rearranged in sorted order.

Constraints

 1 <= n <= 10^5  arr[i] ∈ {0,1,2}

Approach 1 : Brute Force (Counting Method)

Explanation

The simplest way to solve this problem is:

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

This approach is easy to understand but requires multiple traversals.

Steps

  1. Initialize counters:
    • zero
    • one
    • two
  2. Traverse array and count frequencies.
  3. Fill:
    • 0s first
    • then 1s
    • then 2s
  4. Return sorted array.

Dry Run

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

Count values:
0 count = 2
1 count = 2
2 count = 2

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

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

Brute Force Code

Complexity Analysis

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

Space Complexity: O(1)
Explanation:
Only counters are used.

Approach 2 : Optimized Solution (Dutch National Flag Algorithm)

Explanation

The optimized solution uses three pointers:

  • low
  • mid
  • high

The idea is:

  • 0s belong to left side
  • 1s stay in middle
  • 2s belong to right side

This sorts the array in a single traversal.

Steps

  1. Initialize:
    • low = 0
    • mid = 0
    • high = n - 1
  2. Traverse while mid ≤ high.
  3. If arr[mid] == 0:
    • swap low and mid
    • increment both pointers
  4. If arr[mid] == 1:
    • move mid pointer
  5. If arr[mid] == 2:
    • swap mid and high
    • decrement high

Dry Run

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

Initially:
low = 0
mid = 0
high = 5

Traverse 2:
Swap arr[mid] and arr[high]
Array:
[0,0,2,1,1,2]
high = 4

Traverse 0:
Swap arr[low] and arr[mid]
low = 1
mid = 1

Traverse next 0:
Swap again
low = 2
mid = 2

Traverse 2:
Swap with high
Array:
[0,0,1,1,2,2]

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

Optimized Code

Complexity Analysis

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

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

Edge Cases

  1. Array contains only 0s
  2. Array contains only 1s
  3. Array contains only 2s
  4. Array already sorted
  5. Array sorted in reverse order

Why This Problem is Important

This problem helps in understanding:

  1. Dutch National Flag Algorithm
  2. In-place sorting
  3. Pointer manipulation
  4. Partitioning techniques
  5. Efficient traversal

It is one of the most important array sorting interview problems.

Real-World Applications

Partitioning techniques are used in:

  1. Quick Sort
  2. Data categorization
  3. Memory partitioning
  4. Traffic classification
  5. Resource grouping systems

Common Mistakes

  1. Incorrect pointer updates
  2. Forgetting mid pointer handling
  3. Infinite loops
  4. Wrong swap conditions

Interview Tips

Interviewers often expect:

  1. Dutch National Flag Algorithm
  2. O(n) single traversal solution
  3. In-place sorting explanation

Always explain the role of low, mid, and high pointers clearly.

Related Questions

  1. Merge Sorted Arrays
  2. Partition Array
  3. Quick Sort
  4. Move Zeroes
  5. Remove Duplicates

Final Takeaway

The Sort 0s, 1s, and 2s problem is a fundamental array partitioning problem that teaches the Dutch National Flag Algorithm and in-place sorting techniques. Understanding this problem builds a strong foundation for advanced sorting and partition-based interview problems