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

Easy
0/40
Average time to solve is 10m
profile
Contributed by
187 upvotes
Asked in companies
DelhiveryInfo Edge India (Naukri.com)IBM

Problem statement

You have been given an array/list 'arr' consisting of 'n' elements.


Each element in the array is either 0, 1 or 2.


Sort this array/list in increasing order.


Do not make a new array/list. Make changes in the given array/list.


Example : 
Input: 'arr' = [2, 2, 2, 2, 0, 0, 1, 0]

Output: Final 'arr' = [0, 0, 0, 1, 2, 2, 2, 2]

Explanation: The array is sorted in increasing order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line 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: 
The output will print ‘n’ single space-separated integers of the sorted array/list.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
8
2 2 2 2 0 0 1 0


Sample Output 1:
0 0 0 1 2 2 2 2


Explanation of sample input 1 :
The initial array 'arr' is [2, 2, 2, 2, 0, 0, 1, 0].

After sorting the array in increasing order, 'arr' is equal to:
[0, 0, 0, 1, 2, 2, 2, 2]


Sample Input 2:
5
1 1 1 1 1


Sample Output 2:
1 1 1 1 1


Expected time complexity :
The expected time complexity is O(n).


Constraints:
1 <= 'n' <= 10 ^ 4
0 <= 'arr[i]' <= 2

Time limit: 1 second
Hint

Try to sort the array.

Approaches (3)
NAIVE APPROACH

Simply, we will sort the array.

Time Complexity

O(n * log(n)), where ‘n’ is the length of the array/list.

 

Since we are using the inbuilt sort function, the time complexity is O(n * log(n)).

Space Complexity

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

 

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

Code Solution
(100% EXP penalty)
Sort An Array of 0s, 1s and 2s
Full screen
Console