Segregate 0s and 1s

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Move all 0s to left and 1s to right in one pass. Dutch national flag with two values.

Algorithm

1Two pointers: left=0, right=n-1. While left < right: skip 0s from left, skip 1s from right. Swap and advance both.

Common Pitfalls

•O(n) single pass. No auxiliary space. Similar to partition step in quicksort.

Segregate 0s and 1s.java

Java

// Approach: Dutch National Flag (2-way). Two pointers: swap 0s to front and 1s to back.
// Time: O(n) Space: O(1)

class Solution {

    void segregate0and1(int[] arr) {
        int low = 0, n = arr.length;
        int high = n - 1;

        for (int i = 0; i < n && i <= high; i++) {
            if (arr[i] == 0) {
                int temp = arr[low];
                arr[low] = arr[i];
                arr[i] = temp;
                low++;
            }
        }
    }
}

Was this solution helpful?