The Dutch National Flag Problem (The Quicksort "Band-Aid")

Key Takeaways

I kid you not when I say we are in a literal basement no like for real we are actually in a basement I kid you not we are in a basement this might be our whiteboard today we have our exquisite markers the top-of-the-line Ahri marks markers nope we upgraded look at these whiteboards ah so many whiteboards alright so today we have a very interesting problem called the Dutch national flag problem this is also a notable problem in computer science this problem is very similar to the quicksort partitioning scheme that we see in the quicksort algorithm you'll see why shortly so what is the Dutch national flag problem asking us given an array and a pivot index in that array rearrange the elements of the array so that they fall into three categories and they might not always follow to these three categories well they always fall into these three categories but one of the categories might not exist cut the array into an array of elements all before the pivot elements all equal to the pivot and elements all greater than the pivot not that they the index but the value sitting at the pivot index so let's go through examples so we can clearly see what's going on here so I color-coded it green is items less brown is items equal to and read his items greater than the value of the pivot index here is an example here's our example array that indexes are numbered above where you can just count them out yourself if we choose three as the pivot index what value is at nx30 when you need to repartition this array around the value 0 so every value less than 0 needs to be to the left of it every value equal to 0 needs to be grouped together and every value greater than 0 needs to be passed all of the zeros so as you can see here we have all our zeros here ok we have a brown region great and then all the ones you choose are to view to the right to the right of 0 so this creates a kind of coloring like the Dutch national flag duster national flag has three colors so that's kind of where the problems name comes from and in this case we will be missing one of the colors of the flag if our pivot element is the greatest item in the array or it is the least item in the right this is this means that our pivot element is going to be at the edges of the array pushing out one of the colors of the flag so this zero is on the left of the array all items greater than it must be to the right of it so we're only gonna have one color and then the rest so here let's do another example so let's pick pivot index 2 so pivot index 2 we have the value of 2 at pivot index 2 so we have a value of 2 so we need to repartition our array so all numbers less than 2 appear to the left of 2 all numbers equal to 2 stay in the one section and all of the numbers that are greater than 2 are to the right of that middle section here are two valid partitioning schemes that our program could output so for this we see all the zeros and ones are to the left of 2 because they're less than 2 and then we have all our twos in one part and then here we have all our zeros and once again they're in there in their own region and then we have our twos in their own region so the thing is both of these are valid because we partitioned based on these rules everything less than 2 is to the left of it we're fine this is a valid partitioning so this is more perfect than this because we have a sorted order here how are we going to do this how can we do this so there's basically three approaches to this problem all of them use basic array you know swaps and things so let's get into the three approaches to this problem all right so let's look at the three approaches we have to this problem the straightforward solution build three arrays build three arrays both a array of items less than the pivot built an array of items equal to the pivot those an array of items greater than the pivot so what is this going to say this is going to take all of n space because we have n elements and it's going to take we're gonna have to do one pass to build to the three arrays and then another pass to place all of the elements from the arrays that we built back into a to overwrite a to repartition it so this means we're going to have all events space and all event plus of n time which is just going to be linear time overall so that's what we have here so as you can see we have this is our first way we can do it build three arrays and then replace those back into a what is a better way we could do we can do this in place and keep our space constant we don't want to create space that's going to scale with our input so let's keep space constant for next two ways of doing it so the second way we can do it if we can do this with two passes we can do a forward pass to place the elements less than the pivot and a backwards pass to place elements greater than the pivot and in our backwards pass we keep going until we see an item less than the pivot which means we've we've encroached we've we've overstepped into what we've already placed at the beginning we've reached the first color of the flag which is the the region that's less than the pivot and we can stop turning our backwards backwards iteration so 202 linear time passes which would add up to a linear time a linear time run time but in the in the less efficient approach for each element so when I'm here when I'm start here during the forwards pass for each elements I will look for an element that is less than the pivot and place it here and swap my that myself with that item so if my pivot value was 1 I would look for a value less than 1 which is this value so I just keep advancing when I'm here I would scan the whole array for an item that is less than the pivot value I find zero here swap these this is going to be all of N squared in time because for each element for each of the N elements we're going to be doing an layer time o of n pass so n times n we have N squared although it's going to be a triangular number of sorts it's going to still become around like I don't like half I'm squit 1/2 n square we're just N squared in time what do we do how else could we do this well the problem is why are we going to do a whole pass on the whole array to finally make smallest elements to swap ourselves with when in reality we can just do our forwards or backwards pass for the forwards pass example we can just do our forwards pass and just remember where to place the smallest item so let's walk through what I'm saying right now so it becomes very clear we're going to use a placement indicee to repartition when we're going forward and backwards to keep ourself linear in time let's see what I mean all right so now let's walk through it and let's do our forward pass we'll replace the items less than the pivot here is our original array here's the array we're gonna be messing around with our pivot indexes index 1 and the value at index 1 is 1 so we're going to be pivoting around 1 all items less than 1 will be to the left all items equal to 1 will be in in in their own little section and all items greater than 1 will be greater and off to the right so now we're gonna do our little scan on the array and we're gonna keep a placement index so our placement index is right here so we're gonna place right there we're gonna have our arrow let's make that bigger so this is where we're gonna place in the right so we're gonna see we're gonna start it in X 0 and we're gonna compare items and place them in there if they're less than the pivot is 0 less than 1 yes place it and advance our pivot advance our placement all right now we're looking here is 1 less than 1 no is 2 less than 1 no is 0 less than 1 yes so we just swapped index 1 and index 3 as you can see we swap these guys and replace them in here and now we're placing on index 2 we're placing on index 2 now so now okay we just swapped with this now we need to look is 2 less than 1 no is 1 less than 1 no is 1 less than 1 no we're finished with our forward pass and what can you see here all the items less than the pivot are at the beginning of the array all right and now let's go backwards let's move backwards and place all of the items greater than our pivot index value again we're comparing against pivot index 1 which holds the value of 1 so now we're gonna place our placement here so now is one greater than one know is one greater than one no it's two greater than one yes so we'll swap index for an index six all right so then we just swapped index for an index six and now is one greater than one no it's two greater than one two is greater than one let's do another swap all right so we just swapped index two and index five and now our new placement is at index 4 we're gonna place our neck here our greatest item there and you see how we're remembering where our placement needs to go instead of doing a scan every time that's how we took it from all events square to linear oh of n now so now we're here and we just did we just did a flip here and now we hit zero is zero greater than one well zero is less than the pivot index down zero is less than the pivot of X and now we are encroaching on what we already did we're already stepping into the lesser region this is when our backwards iteration stops we end our backwards iteration and now if you notice our problem is finished we have two we have three sections and now you can see we have our Dutch national flag we have the region less than our pivot value or pivot and x1 value of one we have our region equal to one and we ever read u greater than one so this is the Dutch national flag interview problem this is how you approach it this is how we took it from using a ton of space to doing all of N squared to realize in weight we could just use a placement pointer to remember where our placements go and just do our forwards and backwards scan and place items this is the problem and if you liked this video hit the like button subscribe to the channel if you want more interview questions like this and I'm gonna get out of this basement now [Music]