easyArray ProblemsJava

Segregate 0s and 1s in an Array

Rearrange an array of 0s and 1s so all 0s come first and all 1s follow.

Quick Answer

Use a `low` pointer at the start and a `high` pointer at the end. While `low < high`, advance `low` past 0s and pull `high` back past 1s; when `low` sees a 1 and `high` sees a 0, swap them. This groups all 0s before all 1s in one pass, O(n) time and O(1) space.

Problem Statement

Given an array that contains only 0s and 1s, rearrange it in place so that all 0s come before all 1s. You may assume the array holds no other values.

For example, [0, 1, 0, 1, 1, 0] becomes [0, 0, 0, 1, 1, 1].

Input: An integer array arr of length n containing only 0 and 1.

Output: The same array with all 0s at the front and all 1s at the back.

Examples

Example 1
Input:  [0, 1, 0, 1, 1, 0]
Output: [0, 0, 0, 1, 1, 1]

Three 0s move to the front and three 1s settle at the back.

Example 2
Input:  [1, 0, 1, 0]
Output: [0, 0, 1, 1]

The two 0s are pulled forward, leaving the two 1s at the end.

Constraints

  • 0 <= n <= 10^6
  • Every element is either 0 or 1

Think Before You Code

Reveal the questions to ask yourself first
  • Could you just count the 0s and rebuild the array, or partition it with pointers?
  • When the left pointer meets a 1 and the right pointer meets a 0, what single move fixes both?
  • When should the two pointers stop advancing toward each other?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
One approach counts the zeros, then writes that many 0s followed by the rest 1s.
Hint 2
A single-pass approach uses a `low` pointer from the left and a `high` pointer from the right.
Hint 3
Skip 0s from the left and 1s from the right; when both point at misplaced values, swap `arr[low]` and `arr[high]`.

Approach

Reveal the step-by-step approach

Two pointers converging from both ends.

  1. Set low = 0 and high = n - 1.
  2. While low < high:
    • If arr[low] == 0, it is already in place, so increment low.
    • Else if arr[high] == 1, it is already in place, so decrement high.
    • Otherwise arr[low] is 1 and arr[high] is 0, so swap them, then move both pointers inward.
  3. Stop when the pointers cross; all 0s are now left of all 1s.

Every element is looked at once as the pointers close in, so the pass is linear.

Dry Run

Walk through the example step by step

Segregating [0, 1, 0, 1, 1, 0] (low=0, high=5):

low | high | arr[low] | arr[high] | action        | array
----+------+----------+-----------+---------------+------------------
0   | 5    | 0        | 0         | low++         | [0,1,0,1,1,0]
1   | 5    | 1        | 0         | swap, low++,  | [0,0,0,1,1,1]
    |      |          |           | high--        |
2   | 4    | 0        | 1         | low++         | [0,0,0,1,1,1]
3   | 4    | 1        | 1         | high--        | [0,0,0,1,1,1]
3   | 3    | -        | -         | low<high false| [0,0,0,1,1,1]

Solution

Reveal the full Java solution
import java.util.Arrays;

public class SegregateZerosOnes {
    public static void segregate(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            if (arr[low] == 0) {
                low++;
            } else if (arr[high] == 1) {
                high--;
            } else {
                arr[low] = 0;
                arr[high] = 1;
                low++;
                high--;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {0, 1, 0, 1, 1, 0};
        segregate(a);
        System.out.println(Arrays.toString(a)); // [0, 0, 0, 1, 1, 1]

        int[] b = {1, 0, 1, 0};
        segregate(b);
        System.out.println(Arrays.toString(b)); // [0, 0, 1, 1]
    }
}

In the swap branch we know arr[low] is 1 and arr[high] is 0, so writing arr[low] = 0 and arr[high] = 1 is exactly a swap without needing a temporary. The pointers only move inward, each element is visited at most once, and no extra array is allocated — O(n) time, O(1) space.

Time: O(n)Space: O(1)

Common Mistakes

  • Using `<=` in the while condition, which can swap an element with itself at the crossover.
  • Forgetting to move both pointers after a swap, causing an infinite loop.

Edge Cases to Test

  • An array of all 0s or all 1s is already segregated and untouched.
  • An empty or single-element array needs no work.
  • Alternating patterns like [1,0,1,0] must still end fully sorted.

Interview Follow-Ups

  • How would you segregate three distinct values (0s, 1s, and 2s) in one pass?
  • Would a simple counting approach be simpler here, and what is its trade-off?
  • How would you keep the relative order of the 0s stable?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us