# Segregate 0s and 1s (In-Place Sorting)

When I first saw this problem, it looked very simple…

But it actually teaches an important concept:  
**How to optimize from 2 passes → 1 pass using two pointers**

* * *

### **Problem Statement**

You are given an array containing only `0`s and `1`s.

Your task:

*   Move all `0`s to the left
    
*   Move all `1`s to the right
    
*   Do it **in-place**
    

* * *

**Example**

```javascript
Input:  [0, 0, 1, 1, 0]
Output: [0, 0, 0, 1, 1]
```

* * *

### **Approach 1: Two Pass Solution (Counting)**

This is the most intuitive approach.

**Idea**

1.  Count number of `0`s and `1`s
    
2.  Rewrite the array
    

* * *

**Step-by-Step Traversal**

**Input:**

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

**Step 1: Count values**

```plaintext
count0 = 3
count1 = 2
```

**Step 2: Rewrite array**

```plaintext
Index 0 → 0
Index 1 → 0
Index 2 → 0
Index 3 → 1
Index 4 → 1
```

**Final Output:**

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

* * *

**Code**

```javascript
int count0 = 0;
int count1 = 0;

for (int i = 0; i < n; i++) {
    if(arr[i] == 0) count0++;
    else count1++;
}

for (int i = 0; i < count0; i++) {
    arr[i] = 0;
}
for (int i = count0; i < n; i++) {
    arr[i] = 1;
}
```

* * *

**Complexity**

*   Time: **O(n)** (2 passes)
    
*   Space: **O(1)**
    

* * *

### Approach 2: One Pass (Two Pointer Technique)

Now comes the **interesting part**

We solve it in **just one traversal**

* * *

**Idea**

*   Use two pointers:
    
    *   `l` → start
        
    *   `r` → end
        

**Rule:**

*   If `arr[l] == 0` → move `l++`
    
*   If `arr[l] == 1` → swap with `arr[r]`, then `r--`
    

* * *

**Dry Run (Step-by-Step)**

**Input:**

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

**Initial:**

```plaintext
l = 0, r = 4
```

* * *

**Step 1:**

```plaintext
[0, 0, 1, 1, 0]
 L           R

arr[L] = 0 → OK → move L →
```

* * *

**Step 2:**

```plaintext
[0, 0, 1, 1, 0]
    L        R

arr[L] = 0 → OK → move L →
```

* * *

**Step 3 :**

```plaintext
[0, 0, 1, 1, 0]
       L     R

arr[L] = 1 → swap with arr[R]
```

Then:

```plaintext
R--
```

After swap:

```plaintext
[0, 0, 0, 1, 1]
       L  R   
```

* * *

**Step 4:**

```plaintext
[0, 0, 0, 1, 1]
          L  
          R

arr[L] = 0 → move L →
```

* * *

**Step 5:**

```plaintext
[0, 0, 0, 1, 1]
          L  
          R

arr[L] = 1 → swap with arr[R]
```

Then:

```plaintext
R--
```

After swap:

```plaintext
[0, 0, 0, 1, 1]
       R  L   
```

* * *

**Final:**

```plaintext
[0, 0, 0, 1, 1]
Done 
```

* * *

**Code**

```javascript
int l = 0;
int r = n - 1;

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

* * *

**Complexity**

*   Time: **O(n)** (single pass)
    
*   Space: **O(1)**
    

* * *

This problem is a **simplified version of**: Dutch National Flag Problem (0s, 1s, 2s)

If you understand this,  
you can easily solve more complex partitioning problems.

* * *

### Conclusion

| Approach | Passes | Idea |
| --- | --- | --- |
| Counting | 2 | Simple & safe |
| Two Pointer | 1 | Optimized & smart |