Sort array containing only 0, 1 and 2 as elements

Concepts Used:

Sorting

Difficulty Level:

Easy

Problem Statement (Simplified):

We have to print the array containing 0s, 1s and 2s in non-decreasing order.

See original problem statement here

Test Case:

Input:
1
10
0 1 0 0 1 0 2 2 0 1 

Output:
0 0 0 0 0 1 1 1 2 2 

Explanation:
We can get this answer after sorting the whole array.

Solving Approach :

1) Here we can sort the array too but that would cost us at least O(N x log(n)) if we use Merge Sort.

2) We know array contains only three elements i.e. 0s, 1s and 2s, we can count their total number of occurrences in the array.

3) We later can print 0s, 1s and 2s number of times they appear in array by referring some websites to learn programming.

4) For example if 0 appears a times,1 appears b times,and 2 appears c times, then we'll print 0 for a times first then 1 for b times and print 2 for c times aferwards.

Example:

Approach-1 : Using Sorting (Merge Sort)

We can sort array and print it, it takes O(N x log(N))

Let, array A be,

Sorting array A produces our answer that is,

Approach-2 : Using counters

We know, array contains only 0, 1, and 2 as elements, so we find total number of appearances of 0,1, and 2 and print them in order. This take O(N) time complexity.

Let, the array A be,

We maintain hash table H for counting 0, 1, and 2, hash table after counting is,

So our final answer is,

Solutions:

#include <stdio.h>

int main()
{

  int test;
  scanf("%d",&test);

  while(test--){

    int n;
    scanf("%d",&n);

    int arr[n];
    for(int i=0; i<n; i++)
      scanf("%d",&arr[i]);

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

    for(int i=0; i<=2;i++)
      for(int j=0; j<count[i]; j++)
        printf("%d ",i);

    printf("\n"); 
  }
}
#include <bits/stdc++.h>
using namespace std;

int main()
{

  int test;
  cin>>test;

  while(test--){

    int n;
    cin>>n;

    int arr[n];
    for(int i=0; i<n; i++)
      cin>>arr[i];

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

    for(int i=0; i<=2;i++)
      for(int j=0; j<count[i]; j++)
        cout<<i<<" ";

    cout<<endl;
  }
}
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int n = sc.nextInt();

      int arr[] = new int[n];
      for(int i=0; i<n; i++)
        arr[i] = sc.nextInt();

      int count[] = new int[3];
      for(int i=0; i<n; i++)
        count[arr[i]]++;

      for(int i=0; i<=2;i++)
        for(int j=0; j<count[i]; j++)
          System.out.print(i+" ");

      System.out.println(); 
    }

  }
}
Previous post Find sum of elements less than A and greater than B in an array
Next post GCD of two very large numbers

Leave a Reply

Your email address will not be published. Required fields are marked *