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

The simple approach is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array followed by 1’s and 2's. The time complexity of this approach would be O(n) and space complexity O(1).
However, the approach requires two traversals of the array. The question can also be solved in a single scan of the array by maintaining the correct order of 0’s, 1’s, and 2’s using variables.
We divide the array into four groups using three pointers. Let us name these pointers as low, mid, and high.
1. a[0…low-1] only zeroes
2. a[low..mid-1] only ones
3. a[mid…high] unknown
4. a[high+1..n-1] only twos
Algorithm :
1. Initialise three pointers low = 0, mid = 0 and high = n -1
2. Run a while loop until mid<=high :
2.1 If (a[mid] ==0), then swap the element with the element low and increment low and mid (low++ and mid++).
2.2 If (a[mid] ==1), then increment mid (mid++).
2.3 If (a[mid] ==2), then swap it with an element in high range and decrement high (high--).

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);

    }



}

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());

}

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()

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--;

            }

        }



    }



}

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

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--;

        }

    }

}

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 VMware Software Software Developer interview questions & answers

Popular interview questions of Software Developer