Sort an Array of 0s, 1s and 2s

Problem

Given an array arr[] containing only 0s, 1s, and 2s, sort the array in ascending order without using any built-in sort function.

---

My Thought Process

At first, this looks like a normal sorting problem.
But since using built-in sort is not allowed, I needed to think differently.

The key observation is that the array contains only three distinct values.
So instead of general sorting, I can group the elements.

---

Approach (Dutch National Flag Algorithm)

I used three pointers:

• low → position for 0s
• mid → current index
• high → position for 2s

Logic

• If arr[mid] == 0
  Swap with low, then increment both low and mid

• If arr[mid] == 1
  Just increment mid

• If arr[mid] == 2
  Swap with high, then decrement high

---

Code

class Solution {
    public void sort012(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;

        while (mid <= high) {

            if (arr[mid] == 0) {
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;

                low++;
                mid++;
            } 
            else if (arr[mid] == 1) {
                mid++;
            } 
            else {
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;

                high--;
            }
        }
    }
}

---

Complexity

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

---

Key Takeaway

This problem is a classic example of the three-pointer technique.
Instead of applying general sorting, understanding the constraints helps in designing an optimal solution.

--