Home » Technical Interview Questions » Array Interview Questions » Segregate 0s and 1s in an Array

Segregate 0s and 1s in an Array




Difficulty Level Easy

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
Explanation: All 0’s are shifted to left and 1’s are shifted to the right.

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.

READ  Search in Sorted Rotated 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 0th 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.

Segregate 0s and 1s in an 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.

READ  Search an Element in Sorted Rotated Array

Space Complexity

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

Reference

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup