Sort an array of 0s and 1s

Problem Statement: Given an array of length N consisting of only 0s and 1s in random order. Modify the array to segregate 0s on the left and 1s on the right side of the array.

Note: (instead of 0s and 1s we can  also be given with an array of any 2 random integers)

Examples:

Example 1:
Input: N = 5, arr[ ] = {1,0,1,1,0}
Output: {0,0,1,1,1}

Example 2:
Input: N  = 5 , arr[ ] = {1,0,0,0,1}
Output: {0,0,0,1,1}

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Approach:

  • We will traverse the entire array and count the number of 0s , 
  • Once we get the number of zeroes , we can easily the count of 1s as arr.size(_) – count_of_0s
  • Now we will simply fill the array , first we will fill it with 0s till the count_of_0s , then we will fill the 1s

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;
class Solution {
  public:

    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;
    }
};

int main() {
  int n = 5;
  int arr[]={1,0,1,0,1};
  Solution ob;
  cout << "Before Sorting: ";
  for (int a: arr)
    cout << a << " ";
  cout << endl;
  ob.segregate0and1(arr, n);
  cout << "After Sorting: ";
  for (int a: arr)
    cout << a << " ";
}

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n) 

Space Complexity: O(1)

Java Code

import java.util.*;

class Solution {

  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;
  }

  public static void main(String args[]) {
    int n = 5;
    int arr[]={1,0,1,0,1};
    System.out.print("Before Sorting: ");
    for (int a: arr)
      System.out.print(a + " ");
    System.out.println();
    segregate0and1(arr, n);
    System.out.print("After Sorting: ");
    for (int a: arr)
      System.out.print(a + " ");
  }
}

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n) 

Space Complexity: O(1)

Solution 2:

Approach: Two pointer approach

  • Take 2 pointers say s  and e ,one at the beginning and the other at the end of the array
  • Let s point at the beginning of the array and e at the end .
  • Now we want to put all the 1s in the right side of the array , once we do this all 0s will automatically be on the left side of the array
  • So we compare the elements at s , arr[s] =1 then this should be at the right side of the array , so we swap this with element present at e 
  • After swapping , now we know that element at index e will surely be 1 , so now we can decrement e . 
  • Else if theres a 0 then we will increment i 

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;
class Solution {
  public:

    void segregate0and1(int arr[], int n) {
      int type0 = 0;
      int type1 = n - 1;

      while (type0 < type1) {
        if (arr[type0] == 1) {
          swap(arr[type0], arr[type1]);
          type1--;
        } else {
          type0++;
        }
      }
    }
};

int main() {
  int n = 5;
  int arr[]={1,0,1,0,1};
  Solution ob;
  cout << "Before Sorting: ";
  for (int a: arr)
    cout << a << " ";
  cout << endl;
  ob.segregate0and1(arr, n);
  cout << "After Sorting: ";
  for (int a: arr)
    cout << a << " ";
}

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n) 

Space Complexity: O(1)

Java Code

import java.util.*;

class Solution {
    
    static void segregate0and1(int arr[], int n) {
      int type0 = 0;
      int type1 = n - 1;
      int temp;
      while (type0 < type1) {
        if (arr[type0] == 1) {
            temp = arr[type0];
            arr[type0] = arr[type1];
            arr[type1] = temp;
          type1--;
        } else {
          type0++;
        }
      }
    }

public static void main(String args[]) {
  int n=5;
  int arr[]={1,0,1,0,1};
  System.out.print("Before Sorting: ");
  for (int a: arr)
    System.out.print(a+" ");
    System.out.println();
  segregate0and1(arr, n);
  System.out.print("After Sorting: ");
  for (int a: arr)
    System.out.print(a+" ");
}
}

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n) 

Space Complexity: O(1)

Special thanks to Pawan Jumani for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article