Sort 0s 1s and 2s in an Array


Difficulty Level Easy
Frequently asked in Adobe Amazon Hike MakeMyTrip MAQ Microsoft Morgan Stanley Ola Cabs Paytm Qualcomm SAP Labs Snapdeal Walmart Labs Yatra
Array Sort Sorting

Problem Statement

Given an array containing N elements where elements of the array are 0,1 or 2. Sort or Segregate 0s 1s and 2s in an array. Arrange all zeros in the first half, all ones in the second half and all twos in the third half.

Example

Input

22

0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2 0 1

Output

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2

Approach 1

Algorithm

1.    Simply create a count_array of size 3 and initialize all the elements of the array to be zero.
2.    The array element of count_array depicts the number of occurrences of index i.
3.    Traverse the given array and if we get 0 increments the 0th index of count_array and similarly do for 1 and 2 by incrementing the value count_array of 1st and 2nd index.
4.    Finally print the number of 0’s, 1’s, and 2’s as many times as the value of the element of count_array.

Implementation for Sort 0s 1s and 2s in an Array

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int cnt[3]={0};//hashing approach
    for(int i=0;i<N;i++)
    cnt[arr[i]]++;//increase the count of that index 
    for(int i=0;i<3;i++)
    for(int j=0;j<cnt[i];j++)//print that index as many times its value is
      cout<<i<<" ";
  return 0;
}

Java Program

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int cnt[] = new int [3];//hashing approach
        cnt[0]=0;cnt[1]=0;cnt[2]=0;
        for(int i=0;i<n;i++)
        cnt[a[i]]++;//increase the count of that index 
        for(int i=0;i<3;i++)
        for(int j=0;j<cnt[i];j++)//print that index as many times its value is
            System.out.print(i+" ");
       }
}
22
0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2 0 1
0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2

Complexity Analysis

Time Complexity 

O(N) where n is the size of the array. Here we traverse the array and counts the elements of the same type.

Space Complexity

O(1) because we use constant space here.

Approach 2

Algorithm

1.    Simply sort the array (using either Heap/Merge sort or using sort() STL function).
2.    Simply print the sorted array.

Implementation for Sort 0s 1s and 2s in an Array

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    sort(arr,arr+N);//sort the array simply
    for(int i=0;i<N;i++)
    cout<<arr[i]<<" ";
    return 0;
}

Java Program

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        for(int j=0;j<n;j++)
            System.out.print(a[j]+" ");
     }
}
10
0 1 2 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 2

Complexity Analysis

Time Complexity

O(NlogN) because we use the inbuild sort function which has nlogn time complexity.

Space Complexity

O(1) because we don’t use any auxiliary space here.

References