Sort 0s, 1s, and 2s

Problem

You’re given an array of integers and need to sort an array containing only 0s, 1s, and 2s.

---

Strategy

At first, it feels like you can just sort the array or count frequencies.

But the follow-up asks for a one-pass solution with constant space.

Instead, I thought about it differently:
At each position, I asked—

Where should this element go?

So I used three pointers:

• low for placing 0s
• mid for traversal
• high for placing 2s

So for every element:

• If it’s 0 → move it to the front
• If it’s 1 → leave it where it is
• If it’s 2 → move it to the end

This way, everything gets sorted in a single pass.

---

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

---

Key Lines Explained

if arr[mid] == 0:
Move 0 to the front by swapping with the low pointer.

---

elif arr[mid] == 1:
Already in the correct place, just move forward.

---

else:
Move 2 to the end by swapping with the high pointer.

---

Why This Works

We split the array into three parts:

• Left side → all 0s
• Middle → all 1s
• Right side → all 2s

As we traverse, we keep adjusting these regions until the array is sorted.

---

Complexity

Time: O(n)
Space: O(1)

---

Final Note

This problem looks like a sorting problem, but it’s really about placing elements in the right region.

Once you think in terms of positions instead of sorting, the one-pass solution becomes clear.