Sort an Array of 0s and 1s

Given an array consisting of only 0s and 1s, sort the array in ascending order (all 0s first, followed by all 1s). The sorting must be done in-place without using built-in sort.

Example 1

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

Example 2

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

Constraints

• 1 <= arr.length <= 10^6

• arr[i] ∈ {0,1}

Counting Method (Linear Time)

Idea We can simply count how many 0s (and 1s) exist in the array. Once we know that:

• The first count0 positions should be filled with 0s

• The rest should be filled with 1s

That's it, the array becomes sorted!

//---------------Java---------------------
public static void sortCounting(int[] arr) {
    int count0 = 0;
    for (int num : arr) {
        if (num == 0) count0++;
    }
    for (int i = 0; i < count0; i++) {
        arr[i] = 0;
    }
    for (int i = count0; i < arr.length; i++) {
        arr[i] = 1;
    }
}

Complexity Analysis

• Time Complexity: O(n), Single pass to count + another to overwrite
• Space Complexity: O(1), Sorting done in-place

Optimal Approach: Two-Pointer Swap (Single Pass)

we'll solve this problem in a single traversal, without counting, without extra passes and without using any extra space.

This technique is called the Two-Pointer Swap Approach, a pattern used widely in high-performance systems, competitive programming and algorithmic interviews.

Core Idea

We maintain two pointers:

• left : starts from the beginning of the array

• right : starts from the end of the array

The idea is simple:

• If the element at left is already 0, it’s in the correct position -> move left forward.

• If the element at left is 1, it should go to the end -> swap it with arr[right] and move right backward.

This process continues until left < right.

The array gradually gets partitioned into two regions, all 0s on the left and all 1s on the right similar to the partition step of QuickSort.

Step-by-Step Example

Let's dry-run this with a real example:

arr = [1, 0, 1, 0, 0, 1]

//-----------------Java-----------------
public static void sortTwoPointer(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        if (arr[left] == 0) {
            left++;
        } else {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            right--;
        }
    }
}

Complexity Analysis

• Time Complexity: O(n), Each element is checked once
• Space Complexity: O(1), Sorting is done in-place

Complexity Comparison of All Approaches