Sort 0s, 1s, 2s

Easy

0/40

Contributed by

7 upvotes

Asked in companies

Problem statement

You are given an array ‘arr’ consisting only of 0s , 1s, and 2s.

Sort the given array.

For Example:

For ‘arr’ = {1, 0, 0, 2, 1}.
‘Answer’ = {0, 0, 1, 1, 2}.
‘Answer’ should contain all 0s first, then all 1s and all 2s in the end.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer ‘T’, denoting the number of test cases.
For each test case:
The first line contains an integer ‘N’, representing the size of the array ‘arr’.
The second line contains ‘N’ integers, denoting the elements of the array ‘arr’.

Output Format:

For each testcase, return an array ‘Answer’ which contains all the elements of ‘arr’ in sorted order.

Constraints:

1 <=  ‘T’ <= 10^5
1 <= ‘N’ <= 10^5
0 <= ‘arr[i]’ <= 2
Sum of ‘N’ for all testcases <= 10^5

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

0 1 1 2
0 1 1

Explanation of sample output 1:

For Test 1:
For ‘arr’ = {1, 2, 0, 1}.
‘Answer’ = {0, 1, 1, 2}.
In ‘Answer all 0 is placed first, then all the 1s and finally 2.

For Test 2:
For ‘arr’ = {1, 0, 1}.
‘Answer’ = {0, 1, 1}.
In ‘Answer all 0 is placed first, then all the 1s.

Sample Input 2:

Sample Output 2:

0 1 1 2
1 1 2

Hint 1

Hint 2

We can count the number of 0s, 1s and 2s.

Approaches (2)

Approach 1

Approach 2

Counting Approach

Approach:

We can maintain an array ‘count’ where ‘count[i]’ maintains the count of ‘i’ in ‘arr’. Then we can simply iterate through ‘count’ and push ‘i’ ‘count[i]’ times into ‘Answer’.

Algorithm:

Initialise array ‘count’ of size 3
Initialise array ‘Answer’
for ‘i’ from 0 to ‘N-1’:
- count[arr[i]]++
for ‘i’ from 0 to ‘2’:
- while(count[i]--)
  - Answer.push_back(i)
return Answer

Time Complexity

O(N), where ‘N’ is the number of elements in the array ‘arr’.

We are iterating via ‘i’ from 0 to ‘N-1’, hence the overall time complexity of this solution is O(N).

Space Complexity

O(1)

We are only utilising a vector ‘count’ of constant size 3. Thus the space complexity is constant.

(100% EXP penalty)

Sort 0s, 1s, 2s

Console