Segregate 0s and 1s

Given an array that only contains 0s and 1s, rearrange it in place so all the 0s come before all the 1s, in a single pass.

EasyOptionalDutch National FlagTwo Pointers

Solve This Problem

Video Solution

Video coming soon

We're producing a video walkthrough — check back soon.

Problem Overview

Given an array that only contains 0s and 1s, rearrange it in place so all the 0s come before all the 1s, in a single pass.

Why solve this?

A minimal, two-value warm-up for the Dutch National Flag idea — converging boundary pointers that swap elements into place — before Sort Colors adds a third value and a genuinely trickier middle pointer.

Pattern Recognition

Whenever an array holds only a small, fixed set of distinct values and needs to be grouped in place, consider boundary pointers that close in from both ends and swap misplaced elements, rather than counting values and rewriting the array from scratch.

Prerequisites

Move Zeroes — the same in-place partition idea generalized to two boundary pointers.

Hints

You don't need extra space to count 0s and 1s — you can partition in place with two pointers closing in from either end.
Advance the left pointer past any 0 it's already sitting on, and the right pointer past any 1 it's already sitting on.
When left is stuck on a 1 and right is stuck on a 0, swap them and continue.

Approach

Keep a left pointer starting at index 0 and a right pointer starting at the last index. Advance left forward as long as it points at a 0 (it's already correctly placed), and advance right backward as long as it points at a 1 (also already correct). Once left is stuck on a 1 and right is stuck on a 0, those two elements are both misplaced relative to each other, so swapping them fixes both at once. Repeat until left and right cross — at that point every element before left is a 0 and every element from left onward is a 1.

Code

Solution.java

class Solution {
    public void segregate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] == 0) {
                left++;
            } else if (nums[right] == 1) {
                right--;
            } else {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
    }
}

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