DEV Community

Cover image for 🔬Segregate 0's, 1's, and 2's🔬
Kaiwalya Koparkar
Kaiwalya Koparkar

Posted on

🔬Segregate 0's, 1's, and 2's🔬

Question:

Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.

Example 1:

Input: 
N = 5
arr[]= {0 2 1 2 0}
Output:
0 0 1 2 2
Explanation:
0s 1s and 2s are segregated 
into ascending order.
Enter fullscreen mode Exit fullscreen mode

Logic:

  1. Sorting :
    • Take the array and sort it ( Using inbuilt function or by implementation)
    • display the array
  2. Count Technique :
    • Take the inpu in the array
    • declare 3 variables zero, one and two. Count the number of 0's, 1's, 2's from the array and increment the variables accordingly.
    • now run the loop across the array. According to the incrementation of the variable and replace the elements with 0, 1 and 2.
  3. 3 Pointer:
    • Declare three pointers low, mid high
    • mid pointer rotates from low + 1 to high. Use swith case for simplicity
    • if arr [ mid ] is 0 the case will be 1st and it will interchange arr [ low ] and arr [ mid ] . then low ++ and mid ++
    • if arr [ mid ] is 1 the case will be 2nd and there will be only mid++
    • if arr [ mid ] is 2 tthe case will be 3rd and it will interchange arr [ high] and arr [ mid ] . then high - -
    • After the looping print the array.

import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sortingArr[] = new int[n];
        int threePointer[] = new int[n];
        int count[] = new int[n];
        for(int i = 0; i < sortingArr.length; i++){
            sortingArr[i] = sc.nextInt();
            threePointer[i] = count[i] = sortingArr[i];
        }

        //This is solution through sorting
        Arrays.sort(sortingArr);
        System.out.println("Segregation through sorting: ");
        for(int i = 0; i < sortingArr.length; i++){
            System.out.print(sortingArr[i]+" ");
        }

        //This is solution through counting
        int zero = 0;
        int one = 0;
        int two = 0;

        for(int i = 0; i < count.length; i++){
            if(count[i] == 0){
                zero++;
            }else if(count[i] == 1){
                one++;
            }else if(count[i] == 2){
                two++;
            }
        }

        for(int i = 0 ; i < count.length ; i++){
            if(zero != 0){
                count[i] = 0;
                zero--;
            }else if(one != 0){
                count[i] = 1;
                one--;
            }else if(two != 0){
                count[i] = 2;
                two--;
            }
        }

        System.out.println();
        System.out.println("Segregation through counting technique: ");

        for(int i = 0; i < sortingArr.length; i++){
            System.out.print(count[i]+" ");
        }

        //This is solution through 3 pointer
        int lo = 0;
        int hi = threePointer.length - 1;
        int mid = 0, temp = 0;
        while (mid <= hi) {
            switch (threePointer[mid]) {
            case 0: {
                temp = threePointer[lo];
                threePointer[lo] = threePointer[mid];
                threePointer[mid] = temp;
                lo++;
                mid++;
                break;
            }
            case 1:
                mid++;
                break;
            case 2: {
                temp = threePointer[mid];
                threePointer[mid] = threePointer[hi];
                threePointer[hi] = temp;
                hi--;
                break;
            }
            }
        }
        System.out.println();
        System.out.println("Segregation through 3 pointer technique is: ");
        for(int i = 0; i < threePointer.length; i++){
             System.out.print(threePointer[i]+" ");
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)