How to sort all 0s ,1s and 2s in an array in Java

Today we are going to see an array sorting problem which is how to sort all 0s, 1s and 2s in an array in Java. Here we will sort an array full of only 0s, 1s and 2s only. The problem seems easy until we put a condition over this. The condition is to do it O(n) time complexity. This a very a famous and favourite question of the interviewer. There are many solutions to this problem.

Example:

input : 0 1 0 2 0 1

output : 0 0 0 1 1 2

The first solution to this problem is

  1. First, we input the sample array and will declare another array of the same size.
  2. Then we will declare variables like start =0,  end= array size -1;
  3. Then we will start traversing the array and if zero is found it is stored in 2nd array from start.
  4. If 2 is found it will be stored in last.
  5. Then we will again traverse the array to find 1, we will start storing 1 from where the last 0 is stored.
  6. Hence that way array will be sorted.

here is code for the same.

Java program to sort all 0s, 1s and 2s in an array

import java.util.Scanner;
public class sort_0s {

  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
System.out.println("enter the size");
    int n=sc.nextInt();
    int arr[]=new int[n];
	System.out.println("enter the array");
    for(int i=0;i<n;i++)
    {
      arr[i]=sc.nextInt();
    }
    int arr2[]=new int[n];
        
    int k=0, m=n-1 ;
    for(int i=0;i<n;i++)
    { 
      if(arr[i]<1)
       { arr2[k]=arr[i];
      k++;
       }	    
      if(arr[i]>1)
      { arr2[m]=arr[i];
        --m;
      }
       
    }
    int p=k;
    for(int i=0;i<n;i++)
    { 
    if(arr[i]==1)
      {   
      	arr2[p]=arr[i];
      	p++;
      }
    }
    
    System.out.println("sorted array:");
    for(int i1=0;i1<n;i1++)
    {
      System.out.print(arr[i1]+" ");
    }
  }
 
}

Output:

enter the size
5
enter the array
1
1
0
2
0
sorted array:
0 0 1 1 2

Another solution to the problem is:

  1. We will initialize three variable c0, c1 ,c2;
  2. They will act as a counter, co will get increment whenever we find 0 in the array. Similarly, c1 for 1 and c2 for 2.
  3. After counting all 0s, 1s and 2s, we will again iterate the array and will modify the array element. According to the value of c0,c1 & c2.
  4. First, all the os will get arranged then all the 1s and then the 2s.

Here the code for the same

Another way to sort all 0s, 1s and 2s in an array in Java

import java.util.Scanner;

public class sort_0s {

  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    System.out.println("enter the size");
    int n=sc.nextInt();
    int arr[]=new int[n];
    System.out.println("enter the array");
    for(int i=0;i<n;i++)
    {
      arr[i]=sc.nextInt();
      
    }
    int c0=0,c1=0,c2=0;
    for(int i=0;i<n;i++)
    {
      if(arr[i]==0)
        c0++;
      if(arr[i]==1)
        c1++;
      if(arr[i]==2)
        c2++;
      
    }
    int i=0;
    while(c0-->0)
    arr[i++]=0;
     
      while(c1-->0)
        	arr[i++]=1;
        while(c2-->0)
        	arr[i++]=2;
    System.out.println("sorted array:");
    for(int i1=0;i1<n;i1++)
    {
      System.out.print(arr2[i1]+" ");
    }
  }
 
}

Output:

enter the size
5
enter the array
1
1
0
0
2
sorted array:
0 0 1 1 2

The time complexity for both the solution is o(n).

Also read:

Leave a Reply

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