Sort 0s, 1s and 2s (Dutch National Flag Problem)

Sort 0s, 1s and 2s (Dutch National Flag Problem)
Problem Statement
Given an array arr[] containing only 0s, 1s, and 2s, sort the array in ascending order.
Constraint:
You cannot use built-in sort functions.

---

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

Input: arr = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
________________________________________Objective
• Sort array without using sort()
• Use efficient algorithm (one pass preferred)
• Maintain constant extra space

---

Approach 1: Counting Method
Idea
• Count number of 0s, 1s, and 2s
• Overwrite the array accordingly

---

Python Code
arr = [0, 1, 2, 0, 1, 2]

count0 = arr.count(0)
count1 = arr.count(1)
count2 = arr.count(2)

arr = [0]*count0 + [1]*count1 + [2]*count2

print(arr)

---

Complexity
• Time: O(n)
• Space: O(1) (ignoring output array)

---

Approach 2: Dutch National Flag Algorithm (Best Solution)
Idea
Use three pointers:
• low → position for 0
• mid → current element
• high → position for 2

---

Working
• If element is 0 → swap with low, move both pointers
• If element is 1 → move mid
• If element is 2 → swap with high, move high

---

Python Code
arr = [0, 1, 2, 0, 1, 2]

low = 0
mid = 0
high = len(arr) - 1

while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1

elif arr[mid] == 1:
    mid += 1

else:
    arr[mid], arr[high] = arr[high], arr[mid]
    high -= 1

print(arr)

---

Step-by-Step Idea
Initial:
[0, 1, 2, 0, 1, 2]
After processing:
[0, 0, 1, 1, 2, 2]

---

Complexity
• Time: O(n) (single pass)
• Space: O(1)

---

Comparison
Method Time Complexity Space Passes
Counting O(n) O(1) 2
Dutch Flag O(n) O(1) 1 ✅

---

Edge Cases
• All elements same → [0,0,0]
• Already sorted array
• Reverse sorted array

---

Final Thoughts
• Best approach is Dutch National Flag Algorithm
• Very important for interviews
• Demonstrates:
o Pointer manipulation
o In-place sorting
o Optimization thinking