# 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](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:

```plaintext
0 
1 
2
```

Your task:

*   Sort the array **in-place**
    
*   Order should be: `0s → 1s → 2s`
    

* * *

**Example**

```plaintext
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 `0`s, `1`s, and `2`s
    
2.  Rewrite the array
    

* * *

**Dry Run**

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

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

Now rewrite:

```plaintext
[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:**

```plaintext
[2, 0, 2, 1, 1, 0]
```

* * *

**Initial**

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

* * *

**Step 1 :**

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

Only `r--`, Don’t move `i`

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

* * *

**Step 2 :**

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

**Move both:**

```plaintext
l++, i++
```

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

* * *

**Step 3 :**

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

**Move:**

```plaintext
l++, i++
```

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

* * *

**Step 4 :**

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

**Only:**

```plaintext
r--
```

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

* * *

**Step 5 :**

```plaintext
arr[i] = 1
```

Just:

```plaintext
i++
```

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

* * *

**Step 6 :**

```plaintext
arr[i] = 1 
→ move forward
```

```plaintext
i++
```

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

* * *

**Done**

```plaintext
i > r → stop
```

* * *

**Final Output**

```plaintext
[0, 0, 1, 1, 2, 2]
```

* * *

### Key Rules (Remember This)

### If `arr[i] == 0`

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

* * *

### If `arr[i] == 1`

```plaintext
i++;
```

* * *

### If `arr[i] == 2`

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

* * *

**Code**

```plaintext
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