Sort An Array of 0s, 1s and 2s
You have been given an array/list ARR consisting of ‘N’ elements. Each element in the array is either 0, 1 or 2.

Now, your task is to sort this array/list in increasing order. For example, if ARR = [0, 2, 1, 1], then after sorting ARR must look like [0, 1, 1, 2].

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first line of each test case contains a positive integer ‘N’ which represents the length of the array/list. The second line of each test case contains ‘N’ single space-separated integers representing the elements of the array/list.

Output Format:

For each test case, the only line of output will print ‘N’ single space-separated integers of the sorted array/list. Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Sort An Array of 0s, 1s and 2s

You have been given an array/list ARR consisting of ‘N’ elements. Each element in the array is either 0, 1 or 2.

Now, your task is to sort this array/list in increasing order. For example, if ARR = [0, 2, 1, 1], then after sorting ARR must look like [0, 1, 1, 2].

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a positive integer ‘N’ which represents the length of the array/list.

The second line of each test case contains ‘N’ single space-separated integers representing the elements of the array/list.

Output Format:

For each test case, the only line of output will print ‘N’ single space-separated integers of the sorted array/list.  

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
0 <= ARR[i] <= 2

Time limit: 1 sec

Accepted Answer

Tip 1 : Practice array traversals and pointers
Tip 2 : try to optimise always
Tip 3 : being with brute force approach and slowly remove the repetition in approach

Accepted Answer

NAIVE APPROACH

Simply, we will sort the array.

Space Complexity: O(1)Explanation:

O(1), i.e. constant space complexity.

Since we are not using any extra space. Hence, the space complexity is constant.

Time Complexity: O(nlogn)Explanation:

O(Nlog(N)), where N is the length of the array/list.

Since we are using the inbuilt sort function. Hence, the time complexity is O(Nlog(N)).

Java (SE 1.8)

/*

    Time Complexity : O(Nlog(N))

    Space Complexity : O(1)



    where N is the length of the array/list.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static void sortArray(ArrayList arr, int n) {

        Collections.sort(arr);

    }



}

Python (3.5)

'''

    Time Complexity : O(NlogN)

    Space Complexity : O(1)



    where N is the length of the array/list.

'''





def sortArray(arr, n):

    

    arr.sort()

C++ (g++ 5.4)

/*

    Time Complexity : O(Nlog(N))

    Space Complexity : O(1)



    where N is the length of the array/list.

*/





#include



void sortArray(vector& arr, int n)

{

    sort(arr.begin(), arr.end());

}

Accepted Answer

COUNT 0, 1 and 2

A two-pass algorithm can easily solve the problem. We will count the number of 0s, 1s and 2s in the array/list.

Then, we will overwrite the array with the total number of 0s, followed by 1s and 2s, respectively.

Space Complexity: O(1)Explanation:

O(1), i.e. constant space complexity.

We are using only three variables to store the count of 0s, 1s and 2s.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the array/list.

We are iterating over the array/list twice, first to count the 0s, 1s and 2s and then during overwriting them in the array. Hence, the time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static void sortArray(ArrayList arr, int n) {

        int one = 0;

        int zero = 0;

        int two = 0;



        for (int i = 0; i < n; i++) {

            if (arr.get(i) == 0) {

                zero++;

            } else if (arr.get(i) == 1) {

                one++;

            } else {

                two++;

            }

        }



        int index = 0;



        while (zero-- > 0) {

            arr.set(index, 0);

            index++;

        }



        while (one-- > 0) {

            arr.set(index, 1);

            index++;

        }



        while (two-- > 0) {

            arr.set(index, 2);

            index++;

        }

    }



}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

'''





def sortArray(arr, n):

    

    zero = 0

    one = 0

    two = 0



    for i in range(n):

        if arr[i] == 0:

            zero += 1



        elif arr[i] == 1:

            one += 1



        else:

            two += 1





    index = 0



    while zero > 0:

        arr[index] = 0

        index += 1

        zero -= 1



    while one > 0:

        arr[index] = 1

        index += 1

        one -= 1



    while two > 0:

        arr[index] = 2

        index += 1

        two -= 1

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

*/



void sortArray(vector& arr, int n)

{

    int zero = 0;

    int one = 0;

    int two = 0;



    for (int i = 0; i < n; i++)

    {

        if (arr[i] == 0)

        {

            zero++;

        }

        else if (arr[i] == 1)

        {

            one++;

        }

        else

        {

            two++;

        }

    }



    int index = 0;



    while (zero--)

    {

        arr[index] = 0;

        index++;

    }



    while(one--)

    {

        arr[index] = 1;

        index++;

    }



    while(two--)

    {

        arr[index] = 2;

        index++;

    }

}

Accepted Answer

THREE-POINTER APPROACH

We can sort the array in one-pass by maintaining three positional pointers ‘zeroPos’, ‘onePos’ and ‘twoPos’ initialised to 0, 0 and N-1, respectively.

Here, ‘zeroPos’ represents the first 1 after all 0s, ‘onePos’ represents the current element, and ‘twoPos’ represents the last unexplored element before all 2s.

Now, we iterate through ARR with ‘onePos’-

If we encounter a 0.
- We will swap arr[zeroPos] and arr[onePos].
- This is because ‘zeroPos’ represents the first 1 after all 0s and we have to ensure that all 0s must come before 1.
- Then increment ‘zeroPos’ and ‘onePos’ by 1.
Else, If we encounter a 1.
- We will simply increment ‘onePos’ by 1.
Else, If we encounter a 2.
- We will swap arr[onePos] and arr[twoPos].
- This is because ‘twoPos’ represents the last unexplored element before all 2s and we have to ensure that all 2s must come after 1.
- Then decrement ‘twoPos’ by 1.

Space Complexity: O(1)Explanation:

O(1) i.e. constant space complexity.

We are using only three-pointers ‘zeroPos’, ‘onePos’ and ‘twoPos’.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the array/list.

We are iterating over the array/list only once. Hence, the time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static void sortArray(ArrayList arr, int n) {

        int zeroPos = 0;

        int onePos = 0;

        int twoPos = n - 1;



        while (onePos <= twoPos) {

            if (arr.get(onePos) == 1) {

                onePos++;

            } else if (arr.get(onePos) == 0) {

                Collections.swap(arr, zeroPos, onePos);

                zeroPos++;

                onePos++;

            } else {

                Collections.swap(arr, twoPos, onePos);

                twoPos--;

            }

        }



    }



}

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

*/



void sortArray(vector& arr, int n)

{

    int zeroPos = 0;

    int onePos = 0;

    int twoPos = n-1;



    while (onePos <= twoPos)

    {

        if (arr[onePos] == 1)

        {

            onePos++;

        }

        else if (arr[onePos] == 0)

        {

            swap(arr[zeroPos], arr[onePos]);

            zeroPos++;

            onePos++;

        }

        else

        {

            swap(arr[onePos], arr[twoPos]);

            twoPos--;

        }

    }

}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of the array/list.

'''





def sortArray(arr, n):

    

    zeroPos = 0

    onePos = 0

    twoPos = n - 1



    while onePos <= twoPos:

        if arr[onePos] == 1:

            onePos += 1



        elif arr[onePos] == 0:

            arr[zeroPos], arr[onePos] = arr[onePos], arr[zeroPos]

            

            zeroPos += 1

            onePos += 1



        else:

            arr[onePos], arr[twoPos] = arr[twoPos], arr[onePos]

            

            twoPos -= 1

You have been given an array/list ARR consisting of ‘N’ elements. Each element in the array is either 0, 1 or 2.

Now, your task is to sort this array/list in increasing order. For example, if ARR = [0, 2, 1, 1], then after sorting ARR must look like [0, 1, 1, 2].

Input Format:

Output Format:

Note:

Constraints:

Top Flipkart SDE-2 interview questions & answers

Popular interview questions of SDE-2

Top HR questions asked in Flipkart SDE-2