Sort 0, 1, 2 (Dutch National Flag Algorithm)

When I first solved the 0s and 1s segregation problem, it felt simple.

If you haven’t seen it, you can check it here:
🔗 https://shubhamsinghbundela.hashnode.dev/segregate-0s-and-1s-in-place-sorting

But then comes this problem — Sort an array of 0s, 1s, and 2s in one pass

---

Problem Statement

You are given an array containing only:

0 
1 
2

Your task:

• Sort the array in-place

• Order should be: 0s → 1s → 2s

---

Example

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

---

Approach 1: Counting (Two Pass)

Idea

This is the most straightforward way:

1. Count number of 0s, 1s, and 2s

2. Rewrite the array

---

Dry Run

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

Count:
0 → 2 times
1 → 2 times
2 → 2 times

Now rewrite:

[0, 0, 1, 1, 2, 2]

---

Complexity

• Time: O(n) (2 passes)

• Space: O(1)

---

Approach 2: Dutch National Flag (One Pass)

Now comes the real interview approach

---

Idea

• Use two pointers:

  • l → start

  • i → start

  • r → end

Rule:

• If arr[i] == 0 → swap arr[i] with arr[l] , then move i++, l++

• if arr[i] == 1 -> move i++

• If arr[i] == 2 → swap arr[i] with arr[r], then r--

---

Step-by-Step Dry Run

Input:

[2, 0, 2, 1, 1, 0]

---

Initial

[2, 0, 2, 1, 1, 0]
 l
 i
                r

---

Step 1 :

arr[i] = 2 
swap with arr[r]

Only r--, Don’t move i

[0, 0, 2, 1, 1, 2]
 l
 i
             r

---

Step 2 :

arr[i] = 0 
→ swap with arr[l]

Move both:

l++, i++

[0, 0, 2, 1, 1, 2]
    l
    i
             r

---

Step 3 :

arr[i] = 0 
→ swap with arr[l]

Move:

l++, i++

[0, 0, 2, 1, 1, 2]
       l
       i
             r

---

Step 4 :

arr[i] = 2 
→ swap with arr[r]

Only:

r--

[0, 0, 1, 1, 2, 2]
       l
       i
          r

---

Step 5 :

arr[i] = 1

Just:

i++

[0, 0, 1, 1, 2, 2]
       l
          i
          r

---

Step 6 :

arr[i] = 1 
→ move forward

i++

[0, 0, 1, 1, 2, 2]
       l
             i
          r

---

Done

i > r → stop

---

Final Output

[0, 0, 1, 1, 2, 2]

---

Key Rules (Remember This)

If arr[i] == 0

swap(arr[l], arr[i]);
l++;
i++;

---

If arr[i] == 1

i++;

---

If arr[i] == 2

swap(arr[i], arr[r]);
r--;

---

Code

int i = 0;
int l = 0;
int r = n - 1;

while(i <= r){
    if(arr[i] == 0){
        swap(arr[l], arr[i]);
        l++;
        i++;
    } 
    else if(arr[i] == 1){
        i++;
    } 
    else{
        swap(arr[i], arr[r]);
        r--;
    }
}

---

Complexity

• Time: O(n) (single pass)

• Space: O(1)

---

Final Thoughts

If you understood this problem:

You now understand:

• Two pointer technique

• In-place partitioning