I was going through LeetCode problems that I have solved, looking for one that would be good to write a post about. I came across the Dutch National Flag Problem and knew right away that it would be a good one.
LeetCode says that I solved this one on December 12, 2020 at 18:04. I remember this one because I was able to solve it all on my own. Being able to solve a problem all by yourself, certainly is powerful positive reinforcement. I certainly can use a bit of a pick-me-up after last night’s LeetCode Contest. I was only able to answer one question! Oh well, there is always next week.
Before we get into the problem, I just wanted to give some background on it. It was actually first created by Edsger W. Dijkstra. Pretty neat if you ask me. Read more about it here.
Given an array nums with 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.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
Input: nums = [2,0,2,1,1,0]
Input: nums = [2,0,1]
Input: nums = 
Input: nums = 
How to Solve
A good way to think about this problem is to realize that there are three different possible numbers (or colors) that can be in the array. As the array is iterated through, a different action needs to occur for each of the different numbers.
The twos need to all be at the right end of the output array, the zeros need to be all at the left end of the output array, and the ones need to be in the middle.
One of my initial thoughts for this problem was that there would have to be multiple pointers. One pointer to keep track of the lower bound, one for the upper bound, and then one that iterates. The pointers for the bounds will only increment or decrement, when the position that corresponds to that pointer is sorted properly.
Here are the steps:
- If the current number is zero, then swap the current number with the number at the lower bound. Increase the lower bound and current index by one.
- If the current number is one, increase only the current index by one.
- If the current number is two, swap the current number with the number at the upper bound. Decrease the upper bound by one.
- Repeat that process until the index for current passes the upper bound index value.
Here is the code that I came up with. Might not be a one-liner, but I still am pretty proud of it. If you want to see some other solutions, here is a top-rated one and here is another top-rated one too.
I find illustrations pretty helpful to better understand the steps involved in an algorithm. Let’s look at some illustrations to help us be able to see this algorithm in action.
Input: [2, 1, 0, 0, 1, 2]
Figure A shows the initial setup. The left is 0, current is 0, and right is 5. nums[current] = 2 and nums[right] = 2, so just right is decremented by one.
In Figure B, once again nums[current] = 2, but this time nums[right] = 1. These two values will be swapped. right is decreased by one.
In Figure C, nums[current] = 1, so only current is increased by one.
In Figure D, nums[current] = 1, so current is again increased by one.
In Figure E, nums[current] = 0, so nums[current] is swapped with nums[left] and then both left and current are increased by one.
In Figure F, nums[current] = 0, so nums[current] is swapped with nums[left]. left and current are increased by one. currrent is no longer less than or equal to right, so the while loop terminates and nums is returned as output.
result: [0, 0, 1, 1, 2, 2]
If ‘n’ is the number of elements in the input array, then the time complexity of this algorithm is O(n), as the algorithm only requires one pass.
The space complexity of the algorithm is O(1). The algorithm runs in constant space.
Get Better at Algorithms!
Algorithms and data structures are pretty tough. They are definitely taking a while for me to get the hang of them. However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me. If I missed any that have been helpful to you, be sure to mention them in the comments.
- Cracking the Coding Interview – Great resource. Really gets you in the right mindset for interviews. You can find it here.
- Elements of Programming Interviews – Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
- Grokking the Coding Interview – Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
- Grokking Dynamic Programming – Dynamic programming is tough. This course has definitely helped me get a better understanding.
- Tushar Roy – Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
- Back To Back SWE – Great YouTube Channel. Highly recommend.
- Kevin Naughton Jr. – Another awesome YouTube channel. Great at going over problems and gives helpful advice.
- Base CS – Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
- Coding Challenge Website – There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
- Pramp – Do mock interviews! The sooner the better! Pramp has been a huge help to me.
Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!
This question is an example of why I consider coding interviews to be overblown. An obvious (and simpler) solution is counting sort. We make one pass and count the number of 0, 1 and 2s; in the next pass, we put them in their places. Linear time, no need to keep track of multiple pointers.
This is a great solution that you are suggesting. Linear time and constant space. I agree it is a more simple and intuitive approach than the one that I posted. Only reason, I didn’t post that solution is because LeetCode was looking for a one-pass solution. One-pass and two-pass are both considered linear.
So unless the interviewer specifies that they are looking for a one-pass solution, I would go with your approach, otherwise go with mine. I should have mentioned this in the post.
I was asked this question in my interview and i failed miserably. After going through the solution, I am just breaking my head thinking how can one come up with this solution without coming across it before.
What inspired you to come up with solution? Any previous problem that is similar to this..
I think I was able to come up with this solution by having done similar problems previously. I remember having figured out the solution that I posted, but having to look up the other two popular solutions to this problem. I could have easily not gotten the solution that I got though. There were many problems that I wasn’t able to get and had to look up to the solutions to. The important thing is is that you learn from the solutions and learn how to apply the lessons to future problems.
The key is to just do lots of problems. You will start to see patterns and be able to solve problems more easily once you have seen enough patterns. Here are some more problems that are similar to this one. If you are struggling with any particular kind of problem then just use the tags or groups on the popular algorithm sites and focus on those kind of problems.