Sort Binary Array

Problem

Sort a binary array (containing only 0s and 1s) in a single pass. This is the two-color variant of the Dutch National Flag problem: partition all 0s to the left and all 1s to the right in-place.

Examples

Example 1

Input: arr = [0, 1, 1, 0, 0, 1]
Output: [0, 0, 0, 1, 1, 1]
Explanation: All zeros moved left, ones moved right.

Example 2

Input: arr = [1, 0, 1, 0, 1]
Output: [0, 0, 1, 1, 1]

Solution

This problem reduces to a single-pass partition: maintain a write pointer z that tracks the position to place the next 0. Iterate once and swap when you see a 0. The algorithm is in-place and stable with O(1) extra space.

Method 1 - Two-pointer partition (single pass)

Intuition

We only need to separate two values (0 and 1). Maintain a pointer z (index of next zero slot). As we scan with index i, when arr[i] == 0 we swap it into position z and increment z. This keeps all zeros on the left in one pass.

Approach

1. Initialize z = 0.
2. For i from 0 to n-1:
   • If arr[i] == 0, swap arr[i] and arr[z], then z++.
3. After the loop, the array is partitioned: all 0s before z, all 1s from z onwards.

Complexity

• ⏰ Time complexity: O(n) – Single pass over the array performs at most n checks and swaps.
• 🧺 Space complexity: O(1) – In-place partitioning with a constant number of extra variables.

Code

C++

#include <vector>
using std::vector;

class Solution {
public:
    void sortBinaryArray(vector<int>& arr) {
        int n = arr.size();
        int z = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 0) {
                std::swap(arr[i], arr[z]);
                ++z;
            }
        }
    }
};

Go

package main

type Solution struct{}

func (s *Solution) sortBinaryArray(arr []int) {
    z := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] == 0 {
            arr[i], arr[z] = arr[z], arr[i]
            z++
        }
    }
}

Java

import java.util.List;
import java.util.Collections;

public class Solution {
    public void sortBinaryArray(int[] arr) {
        int n = arr.length;
        int z = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] == 0) {
                int tmp = arr[i];
                arr[i] = arr[z];
                arr[z] = tmp;
                ++z;
            }
        }
    }
}

Kotlin

class Solution {
    fun sortBinaryArray(arr: IntArray) {
        var z = 0
        for (i in arr.indices) {
            if (arr[i] == 0) {
                val tmp = arr[i]
                arr[i] = arr[z]
                arr[z] = tmp
                z++
            }
        }
    }
}

Python

from typing import List

class Solution:
    def sortBinaryArray(self, arr: List[int]) -> None:
        n: int = len(arr)
        z: int = 0
        for i in range(n):
            if arr[i] == 0:
                arr[i], arr[z] = arr[z], arr[i]
                z += 1

Rust

pub struct Solution;

impl Solution {
    pub fn sort_binary_array(arr: &mut [i32]) {
        let mut z: usize = 0;
        for i in 0..arr.len() {
            if arr[i] == 0 {
                arr.swap(i, z);
                z += 1;
            }
        }
    }
}

Typescript

class Solution {
    sortBinaryArray(arr: number[]): void {
        let z = 0;
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] === 0) {
                const tmp = arr[i];
                arr[i] = arr[z];
                arr[z] = tmp;
                z++;
            }
        }
    }
}