Sort 0s, 1s and 2s

Hi everyone!
Today I solved a very interesting array problem where we need to sort an array containing only 0s, 1s, and 2s — but without using the built-in sort function.

Problem

Given an array of 0s, 1s, and 2s, sort it in ascending order.

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

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

My Approach

At first, sorting seemed like the obvious solution.

But the problem specifically says:
Don’t use built-in sort
So I looked for a better approach

That’s when I learned about the Dutch National Flag Algorithm.

Logic

We use three pointers:

*low - for placing 0s
*mid - current element
*high - for placing 2s

Rules:

*If element is 0 - swap with low, move both
*If element is 1 - just move mid
*If element is 2 - swap with high, move high

---

Code (Python)

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

Time & Space Complexity

Time: **O(n)* (single traversal)
Space: **O(1)* (in-place)

What I Learned

*Not all sorting problems need sorting functions
*Pointer-based approaches can be very efficient
*This is a classic and important algorithm

Thanks for reading!
If you know any other approach, feel free to share.