Last Updated: 5 Aug, 2020
Sort 0 1 2
Easy
Asked in companies
You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.
Note :
Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.
Input format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains an Integer 'N' denoting the size of the array/list.
The second line of each test case contains 'N' space-separated Integers denoting the array/list.
Output format :
For each test case/query, print the sorted array/list(ARR) as space-separated Integers.
Output for every test case will be printed in a separate line.
Note:
You need to change in the given array/list itself. Hence, no need to return or print anything.
Constraints :
1 <= T <= 10
1 <= N <= (5 * (10 ^ 5))
0 <= ARR[i] <= 2
Where 'N' is the size of the given array/list.
And, ARR[i] denotes the i-th element in the array/list.
Time Limit: 1sec
Approaches
Use any good sorting algorithm like Merge Sort, Quick Sort or inbuilt sorting function of different languages.
- Sort the Array and just return.
We can exploit the property that we will only have 0s, 1s and 2s in our array.
- Count the frequency of 0s, 1s and 2s in the array.
- Start from i=0 and first fill the number of 0s present in the array.
- Then fill the number of 1s present in the array.
- Then fill the number of 2s present in the array.
- Finally, we have the sorted array.
We’ll use a three-pointer approach to solve this problem
- The three-pointers will be: current, zeroPos and twoPos.:
- current - This will hold the position of the current element that we’re on during the iteration of the array. This will be initialised to 0.
- zeroPos - This will hold the index where we will push any 0s that we may encounter. This will be initialised to 0.
- twoPos - This will hold the index where we will push any 2s that we may encounter. This will be initialised to n - 1, where n is the size of the array.
- We’ll iterate through the array using the current pointer. Every element is either 0, 1 or 2 so let’s see what we’ll be doing in each of these cases:
- If arr[current] = 0 - In this case, we need to push the element towards the front of the array. To do that we can swap arr[current] and arr[zeroPos], then we will increase both current and zeroPos by 1.
- If arr[current] = 1 - In this case, we will just increase the current by 1, since we are only concerned with push 0s to the front and 2s to the end of the array.
- If arr[current] = 2 - In this case, we need to push the element towards the end of the array. Again, to do this, we’ll just swap arr[current] and arr[twoPos]. We will decrease twoPos by 1. However, in this case, we will not increase the current by 1.
- What will be the condition that must be satisfied so that our loop can end? You might think that it’s when current reaches the end of the array but that’s not the case here. Let’s see why. Can you see what exactly the two pointers, zeroPos and twoPos are doing? As we go through the array, every element before zeroPos is a 0 and every element after twoPos is a 2. Also, every element after zeroPos but before the current is a 1. Therefore, all these elements are ‘sorted’. The element that remains to be sorted is the ones that lie between the indices current and twoPos. Therefore our loop will terminate when the current reaches the value of twoPos.
- Now, let’s understand why we can’t increase the value of current when arr[current] = 2. When we swap arr[current] with arr[twoPos], we don’t know what value was initially at index twoPos (before the swap happened), it could be any of the values 0, 1, or 2. So, we can’t increase the value of current without checking what value was swapped with twoPos. We didn’t have to worry about this in the case where we were swapping arr[current] with arr[zeroPos] because then we would always be swapping 0 and 1.
Similar problems