Rearrange 0s and 1s (In-Place Partition with Two Pointers)

• Rearrange 0s and 1s – partition a binary array in place so all 0s precede all 1s.
• Two-pointer method – a low pointer marks the position where the next 0 should be placed; a scanning pointer sweeps left to right.
• Swap rule – when the scanner finds a 0, swap it with the element at low and advance low.
• Complexity – O(n) time, O(1) space, single pass with no extra array.
• Foundation – this two-value partition generalizes to the Dutch National Flag three-way partition.

What is the Rearrange 0s and 1s problem?

Given an array containing only 0s and 1s, rearrange it in place so that all the 0s come before all the 1s. You must not allocate an extra array. This is a classic two-pointer partitioning problem.

package com.bank.service;

public class Segregate01 {
    public static void segregate(int[] arr) {
        int low = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                int temp = arr[i];
                arr[i] = arr[low];
                arr[low] = temp;
                low++;
            }
        }
    }

    public static void main(String[] args) {
        int[] settlements = {1, 0, 1, 0, 0, 1};
        segregate(settlements);
        for (int s : settlements) System.out.print(s + " ");
    }
}

0 0 0 1 1 1

Why use two pointers instead of counting?

The counting approach first counts how many 0s exist, then overwrites the front of the array with that many 0s and the rest with 1s. That works in two passes and is fine for this specific problem. The two-pointer partition does it in a single pass and generalizes to harder problems.

package com.bank.service;

public class Segregate01Counting {
    // Counting approach: two passes
    public static void segregateCounting(int[] arr) {
        int zeros = 0;
        for (int v : arr) if (v == 0) zeros++;
        for (int i = 0; i < arr.length; i++)
            arr[i] = (i < zeros) ? 0 : 1;
    }
    // Two-pointer: one pass, generalizes to three-way
}

| Aspect | Counting | Two Pointers |
|---|---|---|
| Passes | Two | One |
| Extra space | O(1) | O(1) |
| Generalizes | Only to two values | To three-way (Dutch Flag) |
| Stability | Stable | Not stable |

How does the two-pointer partition work step by step?

The low pointer starts at index 0. The scanning pointer i walks from left to right. Whenever arr[i] is 0, you swap arr[i] with arr[low] and increment low. Whenever arr[i] is 1, you do nothing and let i advance.

By the time the scan finishes, every position before low holds a 0 and every position from low onward holds a 1.

// Walkthrough: arr = [1, 0, 1, 0, 0, 1], low = 0
//
// i=0: arr[0]=1, skip. low=0
// i=1: arr[1]=0, swap(1,0) -> [0, 1, 1, 0, 0, 1], low=1
// i=2: arr[2]=1, skip. low=1
// i=3: arr[3]=0, swap(3,1) -> [0, 0, 1, 1, 0, 1], low=2
// i=4: arr[4]=0, swap(4,2) -> [0, 0, 0, 1, 1, 1], low=3
// i=5: arr[5]=1, skip. low=3
// Result: [0, 0, 0, 1, 1, 1]

What happens when i equals low?

When i equals low, the swap is a self-swap: the element swaps with itself, which is harmless. You do not need a special case to avoid this. The low pointer advances, and the algorithm continues correctly.

// Example: arr = [0, 1, 0], low = 0
// i=0: arr[0]=0, swap(0,0) -> self-swap, no change. low=1
// i=1: arr[1]=1, skip. low=1
// i=2: arr[2]=0, swap(2,1) -> [0, 0, 1]. low=2

How does this extend to the Dutch National Flag?

The Dutch National Flag problem partitions an array of three values (0, 1, 2) using three pointers: low, mid, and high. The current problem is a simplified version with only two values.

package com.bank.service;

public class DutchNationalFlag {
    public static void threeWayPartition(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) {
                swap(arr, low++, mid++);
            } else if (arr[mid] == 1) {
                mid++;
            } else {
                swap(arr, mid, high--);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
}

What about stability?

This partition is not stable. It does not preserve the original relative order of elements within each group. For this problem that does not matter because all 0s are identical and all 1s are identical. If the elements carried extra payload whose order matters, you would need a stable partition instead.

// Unstable example:
// If 0s are tagged: 0a, 0b and 1s are tagged: 1x, 1y
// Input:  [1x, 0a, 1y, 0b]
// Result: [0a, 0b, 1y, 1x]  <- 1x and 1y may swap
// In our case, 0 is 0 and 1 is 1, so instability is invisible

What are common mistakes?

The most common mistake is forgetting to advance the low pointer after a swap, which causes the next 0 to overwrite the previous one.

// WRONG: not advancing low
if (arr[i] == 0) {
    swap(arr, i, low);  // Missing: low++;
}

// CORRECT:
if (arr[i] == 0) {
    swap(arr, i, low);
    low++;
}

Another mistake is trying to use two pointers from opposite ends and doing swaps when left is 1 and right is 0. That works but is slightly more complex and does not generalize as cleanly to the three-way case.

When should you use this technique?

Use this single-pass partition whenever you need to segregate a binary array in place. In banking, this applies to grouping settlement outcomes into failed and cleared batches for downstream processing.

package com.bank.service;

public class SettlementBatchPartition {
    public static void main(String[] args) {
        // 0 = failed, 1 = cleared
        int[] batch = {1, 0, 0, 1, 0, 1, 1, 0};
        Segregate01.segregate(batch);
        // First 'low' entries are failed -> send to recovery
        // Remaining entries are cleared -> send to confirmation
        for (int s : batch) System.out.print(s + " ");
    }
}

0 0 0 0 1 1 1 1

What should a senior engineer know?

A senior engineer should recognize that this two-value partition is the building block for quicksort's partition step and the Dutch National Flag. Keeping the swap logic isolated in a helper method makes it reusable for multi-way partitions.

The time complexity is O(n) because each element is visited once. The space is O(1) because only one pointer variable is needed beyond the scanner.

What are common interview follow-up questions?

• Interviewers commonly ask:
• How would you partition three values (0, 1, 2)? (Dutch National Flag with three pointers.)
• Is this partition stable? (No. Use a stable partition if payload order matters.)
• Can you do it from both ends? (Yes, but one-direction sweep generalizes better.)
• What is the relationship to quicksort? (Quicksort's partition step is this concept applied around a pivot.)