Segregate 0s and 1s in an Array

Problem Statement

Suppose you have an integer array. The problem “Segregate 0s and 1s in an array” asks to segregate the array in two parts, in 0s and in 1s. The 0’s should be on the left side of the array and 1’s on the right side of the array.

Example

arr[]={1,0,1,1,0,1,1,0}

0 0 0 1 1 1 1 1

Algorithm

1. Traverse the array and get the count of total zero’s in the array.
2. Push ‘0’ that

count number of times in the array

.
3. Push ‘1’ (n – count) no of times in the array from the next position of 0 where we left inserting 0.
4. Print the array.

Explanation for Segregate 0s and 1s in an Array

Given the array of the integers, in integers, it will only store the 0s and 1s in the array. Rearrange the array in such a way that all the zeroes will be shifted to the left side of the array and all the 1s elements of the array will be shifted to the right side of the array. For this, we are going to make a count of all the zeroes. That zero counts will be helping us in marking the zeros at the left side of the array.

Traverse the array for the first time in the code to get the count of all the zeroes in the array, this count will be helping us in marking all the count number of places from the left side of the array. So for that we will traverse the array and check for each value of the arr[i], is it is equal to 0, if it is found to be equal to 0, then increase the value of count by 1. We should have declared and initialized the value of count to 0 before entering into the loop. After traversing we got the count.

We will traverse loop count no times, and mark every value of arr[i] from 0^th index to the count-1 number of places. Now, we have the zeroes in the left side of the array. Now we have to traverse the array from the count to n where n is the length of the array. So starting from i=count whatever the value of count will be, keep updating all the values to 1. After all the operations, we have the desired array, 0s in the left side of the array and 1s in the right side of the array.

Implementation

C++ program for Segregate 0s and 1s in an Array

#include<iostream>

using namespace std;

void segregateZeroesOnes(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            count++;
    }
    for (int i = 0; i < count; i++)
        arr[i] = 0;

    for (int i = count; i < n; i++)
        arr[i] = 1;
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {1,0,1,1,0,1,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    segregateZeroesOnes(arr, n);
    printArray(arr, n);

    return 0;
}

0 0 0 1 1 1 1 1

Java program for Segregate 0s and 1s in an Array

class segregateZeroesOnes
{
    public static void segregateZeroesOnes(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
                count++;
        }
        for (int i = 0; i < count; i++)
            arr[i] = 0;

        for (int i = count; i < n; i++)
            arr[i] = 1;
    }
    
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    
    public static void main(String[] args)
    {
        int arr[] = new int[] { 1,0,1,1,0,1,1,0 };
        int n = arr.length;

        segregateZeroesOnes(arr, n);
        printArray(arr, n);

    }
}

0 0 0 1 1 1 1 1

Complexity Analysis for Segregate 0s and 1s in an Array

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.

Reference