Given an array
n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
Here, we will use the integers
2 to represent the color red, white, and blue respectively.
We are given a follow up and told to solve this problem without using the library’s sort function and also whether we can up with a one-pass algorithm using only 0(1) constant space.
Here is an example of how the output should look like once solved
Input: nums = [2,0,2,1,1,0]
This is a leetcode medium level question.common during coding interviews as well! See, the obvious or rather straightforward solution here would be using a counting sort whereby, you first iterate the array counting the numbers of zeros,ones, and twos and then overwriting the array with the total number of zeros,ones and followed by twos. However this solution has a space limitation. It’s space complexity is 0(n) which means it will be need more space should the array be bigger. Hence the reason why we are being asked whether we can come up with a one-pass algorithm using only constant-space
The most optimal way of solving this would be to divide the array into three parts and have a left pointer, current pointer, and right pointer.
Then we will iterate the array and check whether the current pointer is equals to zero and if it is equal we get to swap with the left pointer, at the same time incrementing our current and left pointer.
We also check whether the current pointer is equals to two whereby if it is equal we go ahead and swap the current pointer with the right pointer while decrementing the right.
We will keep doing this until the current pointer is less than or equals to the right pointer. After this is done, our array will get sorted.
Here is the solution in Code:
And there you go! We have solved the problem in constant space using a one pass algorithm. I hope that this article serves to give you a picture of how to approach this problem during coding interviews. For a more detailed description watch how I solve the problem on my channel.
See you on the next coding problem!