Dutch National Flag Problem

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.

The Problem

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.

Examples

Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:
Input: nums = [0]
Output: [0]

Example 4:
Input: nums = [1]
Output: [1]

Link to Problem

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:

1. 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.
2. If the current number is one, increase only the current index by one.
3. If the current number is two, swap the current number with the number at the upper bound.  Decrease the upper bound by one.
4. Repeat that process until the index for current passes the upper bound index value.

The Code

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.

Some Illustrations

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]

Time Complexity

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.

Space Complexity

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!