Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Posted by N.K. Chauhan on Jan 03, 2022

An array A is given, A contains only 0s and 1s in random order. The task is to Segregate 0s on left side and 1s on right side of the array (sort the array) in O(n) time complexity.

Example 1: Segregate 0s and 1s in: {1, 0, 1, 0}

Input: {1, 0, 1, 0}
Output: {0,0,1,1}

Example 2: Segregate 0s and 1s in: {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}

Input: {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}
Output: {0,0,0,0,0,1,1,1,1,1}


Solutions

Method 1: Dutch National Flag

In this approach we will use famous Dutch National Flag algorithm. The idea is to divide the array in two parts such that; [1 to low-1] will have 0s, [low to high-1] will have unsorted elements and [high to n] will have 1s.

Start with low=0, high=n-2 and traverse the array until low

package com.cb.arrays;

import java.util.Arrays;
import java.util.stream.Collectors;

/*
 * O(n)
 * Dutch National Flag
 * */
public class A2_SortArrayContaining01s {
    private static void sort(int[] arr, int n) {
        if (arr == null || n < 1)
            return;

        int low = 0, high = n - 1;
        while (low < high) {
            if (arr[low] == 0)
                low++;
            else if (arr[low] == 1) {
                int tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
                high--;
            }
        }
    }

    // Just to print output array
    private static void printArray(int[] arr) {
        System.out.println(Arrays.stream(arr).mapToObj(Integer::toString).collect(Collectors.joining(",")));
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, 1, 0};
        sort(arr, arr.length);
        printArray(arr);

        int[] arr1 = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0};
        sort(arr1, arr1.length);
        printArray(arr1);
    }
}
0,0,1,1
0,0,0,0,0,1,1,1,1,1

Complexity

The time complexity of this solution is O(n) and space complexity is O(1).

Method 2: Using two indexes to traverse

We can solve this problem in O(n) time using two variables, i=0, j=n-1; The idea is to traverse the array until i

package com.cb.arrays;

import java.util.Arrays;
import java.util.stream.Collectors;

/*
 * O(n), Simple Approach
 * */
public class A2_1_SortArrayContaining01s {

    private static void sort(int[] arr, int n) {
        if (arr == null || n < 1)
            return;

        int i = 0, j = n - 1;
        while (i < j) {
            if (arr[i] == 1) {
                while (arr[j] == 1 && j > i)
                    j--;
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
            i++;
        }
    }

    // Just to print output array
    private static void printArray(int[] arr) {
        System.out.println(Arrays.stream(arr).mapToObj(Integer::toString).collect(Collectors.joining(",")));
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, 1, 0};
        sort(arr, arr.length);
        printArray(arr);

        int[] arr1 = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0};
        sort(arr1, arr1.length);
        printArray(arr1);
    }
}
0,0,1,1
0,0,0,0,0,1,1,1,1,1

Complexity

The time complexity of this solution is O(n) and space complexity is O(1).

Related


Find a triplet in an array that sums to a given number

Two Sum - return index of a pair of array elements with a given sum

Program to print Intersection of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Print all possible permutations of an Array in O(1) space

Program to print Union of two sorted arrays

Word Break Problem (Using HashMap and DP)

Merge two sorted arrays in O(1) space

Longest substring without repeating characters

Print all Subsets (Power Set) of a given array

Rain water trapping problem - O(n) time & O(n) space