ASSIGNMENT 8

1.Sort 0's ,1's AND 2's

Given an array containing only 0s, 1s, and 2s, sort it in-place.
Example:
Id="ex3"
Copy code
Input: [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Approach Used: Dutch National Flag Algorithm
Instead of sorting (O(n log n)), we solve it in one pass (O(n)) using three pointers.

Core Idea
We divide the array into 3 regions:
Copy code

[ 0s | 1s | unknown | 2s ]
↑ ↑ ↑ ↑
low mid ... high

Step-by-step Logic
Initialize pointers
Python id="init"
low = 0
mid = 0
high = len(arr) - 1

Traverse using mid
Python id="logic"
while mid <= high:

Case 1: If element is 0
Python id="case0"
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
--> Move 0 to the left side

Case 2: If element is 1
Python id="case1"
mid += 1
--> Already in correct position

Case 3: If element is 2
Python id="case2"
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
--> Move 2 to the right side
!Don’t increment mid here (important!)

Full Code
`class Solution:
def sort012(self, arr):
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`

Complexity Analysis
Time Complexity: O(n) (single pass)
Space Complexity: O(1) (in-place)
-->This is optimal—you can’t do better than this.

Why don’t we increment mid when swapping with high?
-->Because the swapped element from the end is unknown, so we must check it again.

Conclusion
The Dutch National Flag algorithm is:
Efficient
In-place
One-pass
-->This makes it the best solution for this problem.