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 0s and 1s.

Your task:

• Move all 0s to the left

• Move all 1s to the right

• Do it in-place

---

Example

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 0s and 1s

2. Rewrite the array

---

Step-by-Step Traversal

Input:

[0, 0, 1, 1, 0]

Step 1: Count values

count0 = 3
count1 = 2

Step 2: Rewrite array

Index 0 → 0
Index 1 → 0
Index 2 → 0
Index 3 → 1
Index 4 → 1

Final Output:

[0, 0, 0, 1, 1]

---

Code

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:

[0, 0, 1, 1, 0]

Initial:

l = 0, r = 4

---

Step 1:

[0, 0, 1, 1, 0]
 L           R

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

---

Step 2:

[0, 0, 1, 1, 0]
    L        R

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

---

Step 3 :

[0, 0, 1, 1, 0]
       L     R

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

Then:

R--

After swap:

[0, 0, 0, 1, 1]
       L  R   

---

Step 4:

[0, 0, 0, 1, 1]
          L  
          R

arr[L] = 0 → move L →

---

Step 5:

[0, 0, 0, 1, 1]
          L  
          R

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

Then:

R--

After swap:

[0, 0, 0, 1, 1]
       R  L   

---

Final:

[0, 0, 0, 1, 1]
Done 

---

Code

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