Software Development

Segregate 0s and 1s in an array


You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array [Basically you have to sort the array]. Traverse array only once. 

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 

Method 1 (Count 0s or 1s) 
Thanks to Naveen for suggesting this method. 
1) Count the number of 0s. So let’s understand with an example we have an array arr = [0, 1, 0, 1, 0, 0, 1] the size of the array is 7 now we will traverse the entire array and find out the number of zeros in the array, In this case the number of zeros is 4 so now we can easily get the number of Ones in the array by Array Length – Number Of Zeros.

2) Once we have counted, we can fill the array first we will put the zeros and then ones (we can get number of ones by using above formula).

C++

#include <bits/stdc++.h>

using namespace std;

  

void segregate0and1(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 print(int arr[], int n)

{

    cout << "Array after segregation is ";

  

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  

int main()

{

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

    int n = sizeof(arr) / sizeof(arr[0]);

  

    segregate0and1(arr, n);

    print(arr, n);

    return 0;

}

  

C

#include <stdio.h>

  

void segregate0and1(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 print(int arr[], int n)

{

    printf("Array after segregation is ");

    for (int i = 0; i < n; i++)

        printf("%d ", arr[i]);

}

  

int main()

{

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

    int n = sizeof(arr) / sizeof(arr[0]);

  

    segregate0and1(arr, n);

    print(arr, n);

    return 0;

}

  

Java

import java.io.*;

public class GFG {

      

    

    static void segregate0and1(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;

    }

      

    

    static void print(int arr[], int n)

    {

        System.out.print("Array after segregation is ");

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");    

    }

      

    

    public static void main(String[] args)

    {

        int arr[] = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.length;

  

        segregate0and1(arr, n);

        print(arr, n);

          

    }

}

  

Python3

  

def segregate0and1(arr, n) :

      

    

    count = 0 

  

    for i in range(0, n) :

        if (arr[i] == 0) :

            count = count + 1

  

    

    for i in range(0, count) :

        arr[i] = 0

  

    

    for i in range(count, n) :

        arr[i] = 1

          

  

def print_arr(arr , n) :

    print( "Array after segregation is ",end = "")

  

    for i in range(0, n) :

        print(arr[i] , end = " ")

          

  

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

n = len(arr)

      

segregate0and1(arr, n)

print_arr(arr, n)

  

  

          

C#

using System;

  

class GFG {

      

    

    static void segregate0and1(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;

    }

      

    

    static void print(int []arr, int n)

    {

        Console.WriteLine("Array after segregation is ");

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " "); 

    }

      

    

    public static void Main()

    {

        int []arr = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.Length;

  

        segregate0and1(arr, n);

        print(arr, n);

          

    }

}

  

PHP

<?php

  

function segregate0and1(&$arr, $n)

{

    $count = 0;

                

  

    for ($i = 0; $i < $n; $i++) 

    {

        if ($arr[$i] == 0)

            $count++;

    }

  

    

    

    for ($i = 0; $i < $count; $i++)

        $arr[$i] = 0;

  

    

    

    for ($i = $count; $i < $n; $i++)

        $arr[$i] = 1;

}

  

function toprint(&$arr , $n)

{

    echo ("Array after segregation is ");

  

    for ($i = 0; $i < $n; $i++)

        echo ( $arr[$i] . " ");

}

  

$arr = array(0, 1, 0, 1, 1, 1 );

$n = sizeof($arr);

  

segregate0and1($arr, $n);

toprint($arr, $n);

      

?>

Javascript

<script>

  

function segregate0and1(arr, n) 

    let count = 0;

  

    for (let i = 0; i < n; i++) { 

        if (arr[i] == 0) 

            count++; 

    

  

    

    for (let i = 0; i < count; i++) 

        arr[i] = 0; 

  

    

    for (let i = count; i < n; i++) 

        arr[i] = 1; 

  

function print(arr, n) 

    document.write("Array after segregation is "); 

  

    for (let i = 0; i < n; i++) 

        document.write(arr[i] + " "); 

  

  

    let arr = [ 0, 1, 0, 1, 1, 1 ]; 

    let n = arr.length; 

      

    segregate0and1(arr, n); 

    print(arr, n); 

      

  

  

</script>

Output

Array after segregation is 0 0 1 1 1 1 

Time Complexity : O(2n)  ≅ O(n)
Auxiliary Space: O(1)

Method 1 traverses the array two times. Method 2 does the same in a single pass.

Method 1 has time complexity of O(2n) and Method 2 has time complexity of O(n)

Method 2 (Use two indexes to traverse) 
Maintain two indexes. Initialize the first index left as 0 and second index right as n-1.
Do following while left < right 
a) Keep incrementing index left while there are 0s at it 
b) Keep decrementing index right while there are 1s at it 
c) If left < right then exchange arr[left] and arr[right]

Implementation: 

C++

#include <bits/stdc++.h>

using namespace std;

  

void segregate0and1(int arr[], int size) 

    

    int left = 0, right = size-1; 

  

    while (left < right) 

    

        

        while (arr[left] == 0 && left < right) 

            left++; 

  

        

        while (arr[right] == 1 && left < right) 

            right--; 

  

        

        

        if (left < right) 

        

            arr[left] = 0; 

            arr[right] = 1; 

            left++; 

            right--; 

        

    

  

int main() 

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

    int i, arr_size = sizeof(arr)/sizeof(arr[0]); 

  

    segregate0and1(arr, arr_size); 

  

    cout << "Array after segregation "

    for (i = 0; i < 6; i++) 

        cout << arr[i] << " "

    return 0; 

  

C

#include<stdio.h>

  

void segregate0and1(int arr[], int size)

{

    

    int left = 0, right = size-1;

  

    while (left < right)

    {

        

        while (arr[left] == 0 && left < right)

            left++;

  

        

        while (arr[right] == 1 && left < right)

            right--;

  

        

          

        if (left < right)

        {

            arr[left] = 0;

            arr[right] = 1;

            left++;

            right--;

        }

    }

}

  

int main()

{

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

    int i, arr_size = sizeof(arr)/sizeof(arr[0]);

  

    segregate0and1(arr, arr_size);

  

    printf("Array after segregation ");

    for (i = 0; i < 6; i++)

        printf("%d ", arr[i]);

  

    getchar();

    return 0;

}

Java

import java.io.*;

public class Segregate 

{

    

    void segregate0and1(int arr[], int size) 

    {

        

        int left = 0, right = size - 1;

  

        while (left < right) 

        {

            

            while (arr[left] == 0 && left < right)

               left++;

  

            

            while (arr[right] == 1 && left < right)

                right--;

  

            

               

            if (left < right) 

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

      

    

    public static void main(String[] args) 

    {

        Segregate seg = new Segregate();

        int arr[] = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.length;

  

        seg.segregate0and1(arr, arr_size);

  

        System.out.print("Array after segregation is ");

        for (i = 0; i < 6; i++)

            System.out.print(arr[i] + " ");

    }

}

Python

  

def segregate0and1(arr, size):

    

    left, right = 0, size-1

      

    while left < right:

        

        while arr[left] == 0 and left < right:

            left += 1

  

        

        while arr[right] == 1 and left < right:

            right -= 1

  

        

        

        if left < right:

            arr[left] = 0

            arr[right] = 1

            left += 1

            right -= 1

  

    return arr

  

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

arr_size = len(arr)

print("Array after segregation")

print(segregate0and1(arr, arr_size))

  

C#

using System;

  

class Segregate 

{

    

      

    void segregate0and1(int []arr, int size) 

    {

        

        int left = 0, right = size - 1;

  

        while (left < right) 

        {

            

               

            while (arr[left] == 0 && left < right)

            left++;

  

            

               

            while (arr[right] == 1 && left < right)

                right--;

  

            

               

               

            if (left < right) 

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

      

    

    public static void Main() 

    {

        Segregate seg = new Segregate();

        int []arr = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.Length;

  

        seg.segregate0and1(arr, arr_size);

  

        Console.WriteLine("Array after segregation is ");

        for (i = 0; i < 6; i++)

            Console.Write(arr[i] + " ");

    }

}

  

PHP

<?php

  

function segregate0and1(&$arr, $size)

{

    

    

    $left = 0;

    $right = $size - 1;

  

    while ($left < $right)

    {

        

        

        while ($arr[$left] == 0 && 

               $left < $right)

            $left++;

  

        

        

        while ($arr[$right] == 1 && 

               $left < $right)

            $right--;

  

        

        

        

        

        if ($left < $right)

        {

            $arr[$left] = 0;

            $arr[$right] = 1;

            $left++;

            $right--;

        }

    }

}

  

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

  

segregate0and1($arr, $arr_size);

  

printf("Array after segregation is ");

for ($i = 0; $i < 6; $i++)

    echo ($arr[$i]. " ");

  

?>

Javascript

<script>

  

  

function segregate0and1(arr, size) 

    

    let left = 0, right = size-1; 

  

    while (left < right) 

    

        

        while (arr[left] == 0 && left < right) 

            left++; 

  

        

        while (arr[right] == 1 && left < right) 

            right--; 

  

        

        

        if (left < right) 

        

            arr[left] = 0; 

            arr[right] = 1; 

            left++; 

            right--; 

        

    

  

let arr = [0, 1, 0, 1, 1, 1]; 

let i, arr_size = arr.length; 

  

segregate0and1(arr, arr_size); 

  

document.write("Array after segregation "); 

for (i = 0; i < 6; i++) 

    document.write(arr[i] + " "); 

  

</script>

Output

Array after segregation 0 0 1 1 1 1 

Time Complexity : O(n) 
Auxiliary Space: O(1)

Another approach : 
1. Take two pointer type0(for element 0) starting from beginning (index = 0) and type1(for element 1) starting from end (index = array.length-1). 
Initialize type0 = 0 and type1 = array.length-1 
2. It is intended to Put 1 to the right side of the array. Once it is done, then 0 will definitely towards the left side of the array.

C++

#include <bits/stdc++.h>

using namespace std;

  

void segregate0and1(int arr[], int size)

{

    int type0 = 0;

    int type1 = size - 1;

  

    while (type0 < type1) {

        if (arr[type0] == 1) {

            if (arr[type1] != 1)

                swap(arr[type0], arr[type1]);

            type1--;

        }

        else

            type0++;

    }

}

  

int main()

{

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

    int i, arr_size = sizeof(arr) / sizeof(arr[0]);

  

    segregate0and1(arr, arr_size);

  

    cout << "Array after segregation is ";

    for (i = 0; i < arr_size; i++)

        cout << arr[i] << " ";

  

    return 0;

}

C

#include <stdio.h>

  

void segregate0and1(int arr[], int size)

{

    int type0 = 0;

    int type1 = size - 1;

  

    while (type0 < type1) {

        if (arr[type0] == 1) {

            if (arr[type1] != 1) {

                int temp = arr[type0];

                arr[type0] = arr[type1];

                arr[type1] = temp;

            }

            type1--;

        }

        else

            type0++;

    }

}

  

int main()

{

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

    int i, arr_size = sizeof(arr) / sizeof(arr[0]);

  

    segregate0and1(arr, arr_size);

  

    printf("Array after segregation is ");

    for (i = 0; i < arr_size; i++)

        printf("%d ", arr[i]);

  

    return 0;

}

  

Java

import java.io.*;

import java.util.*;

  

class GFG {

    /**

    Method for segregation 0 and 1 given input array

    */

    static void segregate0and1(int arr[])

    {

        int type0 = 0;

        int type1 = arr.length - 1;

  

        while (type0 < type1) {

            if (arr[type0] == 1) {

                if (arr[type1] != 1) {

                    

                    arr[type1] = arr[type1] + arr[type0];

                    arr[type0] = arr[type1] - arr[type0];

                    arr[type1] = arr[type1] - arr[type0];

                }

                type1--;

            }

            else {

                type0++;

            }

        }

    }

  

    

    public static void main(String[] args)

    {

  

        int[] array = { 0, 1, 0, 1, 1, 1 };

  

        segregate0and1(array);

  

        for (int a : array) {

            System.out.print(a + " ");

        }

    }

}

Python3

  

  

  

def segregate0and1(arr, size):

  

    type0 = 0

    type1 = size - 1

  

    while(type0 < type1):

        if(arr[type0] == 1):

            if(arr[type1] != 1):

              (arr[type0],

               arr[type1]) = (arr[type1],

                              arr[type0])

            type1 -= 1

        else:

            type0 += 1

      

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

arr_size = len(arr)

segregate0and1(arr, arr_size)

print("Array after segregation is"

                         end = " ")

for i in range(0, arr_size):

        print(arr[i], end = " ")

  

C#

using System;

  

class GFG {

  

    

    

    static void segregate0and1(int[] arr)

    {

        int type0 = 0;

        int type1 = arr.Length - 1;

  

        while (type0 < type1) {

            if (arr[type0] == 1) {

                if (arr[type1] != 1) {

                    

                    arr[type1] = arr[type1] + arr[type0];

                    arr[type0] = arr[type1] - arr[type0];

                    arr[type1] = arr[type1] - arr[type0];

                }

                type1--;

            }

  

            else {

                type0++;

            }

        }

    }

  

    

    public static void Main(string[] args)

    {

  

        int[] array = new int[] { 0, 1, 0, 1, 1, 1 };

        segregate0and1(array);

  

        Console.Write("Array after segregation is ");

        foreach(int a in array) { Console.Write(a + " "); }

    }

}

  

PHP

<?php

  

function segregate0and1(&$arr , $size)

{

    $type0 = 0;

    $type1 = $size - 1;

      

    while($type0 < $type1)

    {

        if($arr[$type0] == 1)

        {

              if($arr[$type1] != 1)

            {

              $temp = $arr[$type0];

              $arr[$type0] = $arr[$type1];

              $arr[$type1] = $temp;

            }

            $type1--;

        }

        else

        $type0++;

    }

}

  

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

  

segregate0and1($arr, $arr_size);

  

echo ("Array after segregation is ");

for ($i = 0; $i < $arr_size; $i++)

    echo ($arr[$i] . " ");

  

?>

Javascript

<script>

  

  

function segregate0and1(arr, size)

{

    let type0 = 0;

    let type1 = size - 1;

      

    while (type0 < type1)

    {

        if (arr[type0] == 1)

        {

             if (arr[type1] != 1)

            {   

              

              arr[type1] = arr[type1] + arr[type0];

              arr[type0] = arr[type1] - arr[type0];

              arr[type1] = arr[type1] - arr[type0];

             }

            type1--;

        }

        else

            type0++;

    }

}

  

let arr = [ 0, 1, 0, 1, 1, 1 ];

let i, arr_size = arr.length;

  

segregate0and1(arr, arr_size);

  

document.write("Array after segregation is ");

for(i = 0; i < arr_size; i++)

    document.write(arr[i] + " ");

      

  

</script>

Output

Array after segregation is 0 0 1 1 1 1 

Time complexity: O(n)
Auxiliary Space: O(1)
// Thanks san4net for suggesting this method.
 

Please write comments if you find any of the above algorithms/code incorrect, or a better way to solve the same problem.
 

Last Updated :
22 Jun, 2023

Like Article

Save Article