Dear reader, welcome to a new problem based on Sorting and the two pointer technique. The problem name is 'Sort 012'. It is an extension to the previous problem named 'Sort 01'.
Important Links : Problem link, Solution Video
Dear reader, welcome to a new problem based on Sorting and the two pointer technique. The problem name is 'Sort 012'. It is an extension to the previous problem named 'Sort 01'.
Important Links : Problem link, Solution Video
You are given an array of size n. The array can contain only three types of values, which are 0, 1 and 2. You have to sort this array of 0s, 1s and 2s, i.e. place all the zeros before ones and all the ones before twos.
Note: You are not required to write a stable sort algorithm. It means that the 0's need can be arranged in any order among themselves, and similarly 1's can be in any order among themselves, but must be after 0's only, and the same goes for all the 2's.
Example: If the array is {0, 1, 2, 0, 2, 1, 0, 2, 1}, then the final sorted array should be:
{0, 0, 0, 1, 1, 1, 2, 2, 2}
A O(n log_{2}n) solution based on merge sort/quick sort/ heap sort is very trivial. Just ignore the fact that the array can have only 3 elements 0,1 and 2, and treat it as a normal array and sort it.
I am sure Interviewer will not expect such a solution. Activate your brain cells and think, how can you use the condition that there can be only three types of values in the array to solve the problem in less than O(n logn) time.
A two traversal algorithm which may come to your mind is to first count the number of 0s and 1s in the entire array. Let the count of 0 be zeros and count of 1 be ones. Then traverse the array again, and make the first 'zeros' elements as '0', then the next 'ones' elements as 1, and the remaining (n - zeros - ones) elements as 2. This solution has a O(2 * n) = O(n) time complexity and will take O(1) auxiliary space .
This solution seems perfect, right? I must tell you, friend, that there exists a single-pass algorithm for this problem as well. Let us look at the algorithm.
We will take three pointers: i, j and k, to solve the problem in one traversal. We can maintain four regions or segments of the array using the three pointers.
For each element in the unexplored array, we need to add it to either the array of 1s or the array of 0s or the array of 2s depending on its value. Please note that we will initialize i = 0, j = 0 and k = n-1.
Try to figure out an algorithm! Cases for current elements as 0 or 1 will be similar to the previous problem. But we need to maintain a segment of 2s at the end of the array as well.
Current Element = 1
Current Element = 0
Current Element = 2
Finally, when all the elements are explored from the unexplored array, i.e. the unexplored segment contains 0 elements, then the array is sorted, since there remains only 3 segments: Array of 0s, Array of 1s and Array of 2s respectively. The unexplored segment will contain 0 elements when 'i' becomes equal to k + 1.
Let us take a look at an example and run the algorithm discussed above.
Please try to code this without taking help of the video solution. It will help you develop an insight about the partitioning technique.
java; true";
This code is written and explained by our team in this video. Please refer to it if you are stuck somewhere.
If you analyze carefully then you can see that at each iteration, we are reducing the unexplored segment by 1 element. Hence, we are taking O(n) time only.
Don't get persuaded by three pointers, all moving in different directions. It can be a little confusing that we are having three pointers, still the time complexity is O(n).
Since we are sorting the array in-place, i.e. without taking any extra space, O(1) auxiliary space is required.
This question can be asked in many ways, by changing 0,1 and 2 like:
And so on, but the gist of the algorithm is the same, hence focus on the partitioning technique.
I hope you enjoyed solving the problem with me. I will see you in the next problem: Target Sum Pair - 1, until then Hasta La Vista!