Sort 0s,1s and 2s

**Problem

Given an array containing only 0s, 1s, and 2s, sort it without using built-in sort.**
**
Normal Approach**

Sorting the array
Time: O(n log n) (not optimal)

Best Approach: Dutch National Flag Algorithm
Idea
Divide array into 3 parts:

1. Left → 0s
2. Middle → 1s
3. Right → 2s ** Code**

class Solution:
    def sort012(self, arr):
        low = 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
     return arr

Line-by-Line Explanation
low = mid = 0
We use two pointers starting at 0

low → position to place next 0
mid → current element being checked
Why?

We need to track both placement and traversal
Using one pointer is not enough

high = len(arr) - 1
Points to end of array
Used to place 2s on the right
Why?

We need a pointer from right side also
Without this → cannot move 2s efficiently
while mid <= high
Loop runs until all elements are checked

Why not for loop?

Because high keeps changing
while gives flexible control
if arr[mid] == 0

If current element is 0

Action:

arr[low], arr[mid] = arr[mid], arr[low]
Swap 0 to left side
Why?

Ensures all 0s go to beginning
low += 1 and mid += 1

Move both pointers forward

Why?

low → next position for 0
mid → check next element
elif arr[mid] == 1
If element is 1

Action:
mid += 1
Why?

1 is already in correct middle position
No swap needed → saves time
else: (means arr[mid] == 2)

If element is 2

Action:

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

Why?

Move 2 to right side
Do NOT move mid here
Reason:

New element comes to mid, must recheck
return arr
Return sorted array

Why?

Final result after in-place modification
Time and Space Analysis

⏱ Time Complexity: O(n)
Each element is visited only once
No nested loops
Space Complexity: O(1)
No extra memory used
Sorting done in-place
** Why This Code is Better**

1. One pass only (faster)
2. No extra space
3. No sorting required
4. Efficient swaps only when needed