Dear reader, welcome to a new problem based on Sorting and the two pointer technique. The problem name is '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 01'.
Important Links : Problem link, Solution Video
You are given a binary array of size n. Binary array refers to an array with all elements being either 0 or 1. You have to sort the array, i.e. place all the zeros before all the ones.
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.
Example: If the array is {0, 1, 1, 0, 1, 1, 0, 0, 1}, then the final sorted array should be:
{0, 0, 0, 0, 1, 1, 1, 1, 1}
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 has only 2 elements 0 or 1, 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 two 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 in the entire array. Let the count of zeroes be cnt. Then traverse the array again, and make the first cnt elements as '0', and the rest of n - cnt elements as '1'. 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 the problem. Let us look at the algorithm.
We will take two pointers i and j to solve the problem in one traversal. We can maintain three regions or segments of the array using the two pointers.
For each element in the unexplored array, we need to add it to either the array of 1s or 0s. Please note that we will initialize i = 0 and j = 0 as well.
Current Element = 1
Current Element = 0
Finally, when all the elements are explored from the unexplored array, i.e. the first segment contains 0 elements, then the array is sorted, as first the segment of 0s occurs and then the segment of 1s.
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 two pointer technique.
java; true";
Dry run of the code is explained in the same video, using an example test case.
Come on friend, Give it a try!
It may seem that the time complexity is more than O(n^2) if you consider two pointers as equivalent to nested loops. But, please analyze carefully.
We are reducing the unexplored segment by one element at each iteration. We either add it to the second or third segment. Hence time complexity is O(n) only.
You can also say that both the pointers i and j, move independently for a maximum of n steps, hence time is O(n) only.
Since we are sorting the binary 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 and 1 like:
And so on, but the gist of the algorithm is the same, i.e. partition the array in 3 segments and solve using the concept of 2 pointers.
I hope you enjoyed solving the problem with me. I will see you in the next problem: Sort 012, which is an extension to the current problem. Until then, sayo nara!