Last Updated: 24 Dec, 2022

Sort 0s, 1s, 2s

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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

Solve now

02 Approach

Approach:

We can maintain 3 pointers ‘low’, ‘mid’ and ‘high’. We divide the array into four sections, 0 to ‘low-1’ containing 0s, ‘low’ to ‘mid-1’ containing 1s, ‘mid’ to ‘high-1’ which is unsorted and finally ‘high’ to ‘N-1’ containing 2s. The key idea behind this approach is to send all the 0’s to range [0,’low-1’], all the 1s to range [‘low’,’mid-1’] and all the 2s to range [‘high’,’N-1’].The range [‘mid’, ‘high-1’] contains unprocessed elements. We iterate through ‘arr’ via ‘mid’ while ‘mid’ <= ‘high’. If ‘arr[mid]’ == ‘0’, we swap it with ‘arr[low]’ and increment ‘low’ and ‘mid’. If ‘arr[mid]’ == ‘1’ we increment ‘mid’. If the ‘arr[mid]’ == 2 we swap it with ‘arr[high]’ an ‘high’ (as after the swap ‘arr[mid]’ is unprocessed.).

Algorithm:

Initialise low =0, high =’N-1’ ,mid =0
while(mid <= high)
- if(arr[mid]==0)
  - swap(arr[mid++],arr[low++])
- else if(arr[mid]==1)
  - mid++
- else
  - swap(arr[mid],arr[high--])
return arr

Solve now