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

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
The relevance of this problem is in its applications to quicksort. If we pick bad pivots for quicksort then we will have a O(n^2) runtime which is very bad.
The way of repartitioning an array as shown in O(n) time aids in this issue of repeated elements in an array being sorted.
You can read more here: en.wikipedia.org/wiki/Dutch_n...
The code for this problem is pretty straightforward to do (just 2 for loops, one going forward and one going backward UNTIL we hit the region less than the pivot). If you really want to see the code, this problem can be found in the amazing book Elements of Programming Interviews by Adnan Aziz as question 6.1
++++++++++++++++++++++++++++++++++++++++++++++++++
Question: Write a program that takes an array A and an index i into A, and rearranges the elements such that
1.) All elements less than A[i] (the "pivot") appear first
2.) Followed by elements equal to the pivot
3.) Followed by elements greater than the pivot
Example
A = [0, 1, 2, 0, 2, 1, 1] (same array)
Pivot Index = 2
Valid Output: [0, 1, 0, 1, 1, 2, 2]
Valid Output: [0, 0, 1, 1, 1, 2, 2] (a more perfect output)
This is called Dutch national flag partitioning because the Dutch national flag consists of three horizontal bands, each in a different color.
We will get an input and attempt to form a 3 section partitioning of the array and will always end up with these 3 sections of "lesser", "equal", and "greater" value UNLESS the value at our partition index is the smallest OR greatest value in the array.
Approach 2
Rather than create extra space, we can just do 2 passes, one forward, and then one backward.
During the forward pass for each element in the array, we will look for an element smaller than the element we are at. If it is smaller we would swap ourselves with that element.
During the backward pass move backward and look for an element larger than the element we are at. If it is larger we will swap ourselves with it.
ALSO, we stop moving backward when the element we stand at is less than the pivot because at the point we know that the partitioning is finished.
Complexities:
Time: O(n^2) + O(n^2) = O(n^2)
2 O(n^2) passes. For each element in the array, we do nearly the whole array of comparisons (triangular number) both for the forwards and backward scans.
Space: O(1)
Approach 3
But we don't need to do a new scan for a smaller or larger element FOR EACH element in the array.
We can just have a placement pointer where we swap in "smaller than pivot" values (for the forward iteration) and a "larger than pivot" placement pointer to swap in larger values.
The values equal to the pivot will end up lying in the middle by themselves.
Example
A = [0, 1, 2, 0, 2, 1, 1]
Pivot Index = 1
Value at pivot index is 1.
Forward pass: (looking to place items less than 1)
i = 0 [0, 1, 2, 0, 2, 1, 1] Swap index 0 with index 0
i = 1 [0, 1, 2, 0, 2, 1, 1] (no swap)
i = 2 [0, 1, 2, 0, 2, 1, 1] (no swap)
i = 3 [0, 0, 2, 1, 2, 1, 1] Swap index 1 with index 3
i = 4 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
After backwards pass: (looking to place items greater than 1)
i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 4 [0, 0, 2, 1, 1, 1, 2] Swap index 4 and index 6
i = 3 [0, 0, 2, 1, 1, 1, 2] (no swap)
i = 2 [0, 0, 1, 1, 1, 2, 2] Swap index 2 and index 5
i = 1 [0, 0, 1, 1, 1, 2, 2] (stop*)
*0 is less than the pivot value of 1 so we are now in the region LESS THAN the pivot that we already created in the front of the array
Complexities:
Time: O(n) + O(n) = O(n)
Forward pass with a backwards pass, both running in linear time
Space: O(1)
No auxiliary spaces is created that scales with the input
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++
This question is 6.1 in the fantastic book Elements of Programming Interviews by Adnan Aziz.

[@BackToBackSWE]

Table of Contents: Finding A Room...AGAIN 0:00 - 0:26 Introduction To The Problem 0:26 - 1:22 An Example Of The Partitioning 1:22 - 3:59 Some Approaches To The Problem 3:59 - 7:16 Optimal Solution Walkthrough (Forward) 7:16 - 8:36 Optimal Solution Walkthrough (Backward) 8:36 - 9:44 The Final Solution 9:44 - 10:26 The Wrap Up 10:26 - 10:35 This problem has implications in the improvement of quicksort's worst case O(n^2) runtime cases caused by repeated elements (quicksort has poor performance for inputs that have many repeated elements).

[@ShubhamSinghYoutube]

learning quick sort from A-train , made my day! lol

[@BackToBackSWE]

ye

[@clipzone8302]

Lol A-train's teaching algorithms after retirement from vought

[@kumarshubham9217]

really appreciate your enthusiasm for teaching..you are a great and honest teacher...you put a lot of energy man! keep it up!

[@BackToBackSWE]

thanks ok

[@PiIsRational]

I thought I could figure this out because I am comfortable with the partitioning algorithm in the context of quick sort, but I could not. Thanks for the great explanation. Keep up the great work. Learning a ton on this chan.

[@BackToBackSWE]

sure

[@sachitmohannayak4964]

Wow, this helped me learn the algorithm so quick; the colours are very helpful too.

[@BackToBackSWE]

hahaha nice, glad it did

[@abhinavgupta1492]

This cleared my concept, i was stuck at a quick sort problem. THANKS MAN!!

[@BackToBackSWE]

sure

[@jeezradz]

The best video on dutch national flag on youtube so far! Just subscribed!

[@BackToBackSWE]

thanks and welcome

[@colemanhoyt5437]

The example at the end works so well! Thank you for the explanation!

[@OmniscientPotato]

Thank you for this excellent explanation!

[@BackToBackSWE]

thansk

[@FrancisGabon]

Really like the tone and style of that channel and his presenter! Thanks a lot, great content.

[@zarlorin3728]

this guy is more motivated than my prof in any ways

[@ananyapamde4514]

Really like your videos

[@69shrutivichare60]

Thank you so much This is the only HELPFUL video on 3 way quick sort Please make such more videos 🙏

[@Ghungroo-Beats]

Great Explanation!

[@YavinArba]

informative and engaging, thanks man

[@BackToBackSWE]

sure

[@sidhant4674]

Great work man!

[@BackToBackSWE]

thanks

[@xVermyy]

Bro, great explanation!

[@BackToBackSWE]

Thank you!

[@vaibhavsingh755]

Great Explanation Sir😊

[@PankajKumar-hz3oi]

thanks, brother, great explanation

[@deepaktiwari2847]

You were just FANTASTIC !!

[@BackToBackSWE]

thanks

[@felixongati1840]

One trivial but important optimization, if the position of the current item is on the left of the pivot position, do not swap. i.e. if current_item < pivot and index_current_item < index_pivot, do not swap.

[@jacobzhang840]

Great explanation!

[@BackToBackSWE]

thanks

[@aribakodes5453]

you are a truly amazing teacher

[@BackToBackSWE]

thanks

[@akashsrivastava8324]

Awesome !!!

[@chengjiang7051]

Amazing solution

[@BackToBackSWE]

thx

[@pawehoowicki7940]

very nice!!

[@BackToBackSWE]

thx

[@kumarc4853]

thank you

[@gamingblast2325]

In second way i dont get why its O(n^2) , is the approach is to select every single element and look to element less than it ?

[@khadijakhaldi6468]

Thank you so much for your help! why don't we use the partition step in the quicksort ?

[@BackToBackSWE]

I made this a while back, don't remember the problem 😳

[@khadijakhaldi6468]

haha it’s ok 😁

[@ritikkhatri]

thank you, i couldn't grasp 3 partition before watching.

[@BackToBackSWE]

Glad I could help!

[@prathameshpatil6040]

Can we not do this in one pass? just swap with back or front pointers as per index value ..

[@BackToBackSWE]

Maybe, I dont remember

[@AnantChowdhary]

Yup, we can: public void sortColors(int[] nums) { int filledUpTillFromStart = -1; int filledUpTillFromEnd = nums.length; int i = 0; while(i < nums.length && i < filledUpTillFromEnd) { if(nums[i] == 0) { filledUpTillFromStart++; swap(i, filledUpTillFromStart, nums); if(i == filledUpTillFromStart) i++; } else if(nums[i] == 2) { filledUpTillFromEnd--; swap(i, filledUpTillFromEnd, nums); } else { i++; } } } public void swap(int i, int j, int[] arr) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

[@anveshreddy1245]

Can we apply this algorithm if the arrays number are not only 0 1 2,I mean more unique numbers like array of 1,3,5,6

[@okeuwechue9238]

you can replace single-digit values with a RANGE of values i.e. each single digit transforms to a SET of values

[@doggo660]

wow good job! Thank you.

[@BackToBackSWE]

thanks

[@doggo660]

@@BackToBackSWE I just have one question. Why is the first approach O(n) space complexity if we're just using 3 arrays? Doesn't memory have to grow by n based on input? In that case it's O(1) I think. Space complexity is pretty confusing and not easy to find on the internet.

[@BackToBackSWE]

Each array cannot be larger than n. We bound to O(n) asymptotically because the space we use cannot exceed that linear nature on the tail end of a graph of space usage. For time...we are just doing linear time passes. No nested operations that will tie one variable to another. Is this clear? Continue asking questions.

[@doggo660]

@@BackToBackSWE Ohh ok I think I understand now. So it's O(n) space complexity since n is the size of the array. Therefore, the space is dependent on the size of what array that has been passed in to the function. So really its O(n) auxiliary space since an array by default has an O(n) space complexity.

[@BackToBackSWE]

@@doggo660 yeah.

[@nackyding]

Is the second example the bubble sort algorithm?

[@BackToBackSWE]

can you timestamp it?

[@vitna91]

How do yoi choose the pivot? The value at pivot index should always be 1?

[@BackToBackSWE]

can u timestamp? I made this a while back

[@vitna91]

7:16

[@Dyslexic_Neuron]

finally !!!

[@BackToBackSWE]

hi

[@LalitYadav-vi1ul]

I think the forward and backward scan and replace is Bentley-McIlory 3-way partitioning. But, nice explanation :)

[@BackToBackSWE]

ok

[@ashwin-g-1701]

There is a better way... You do not need to have a separate forward and backwards pass.... This is how its gonna work: You store the indexes to which we have to take the lower than pivot values to, i.e the green pointer in the end of the video, and also another value that stores the index after which, are the greater than pivot values, i.e the red pointer. Let me just call them green and red indexes for now.... -- Now, when you encounter a value < pivot, exchange with green index, increment green index and go on to check the next value. -- When you encounter a value = pivot, ignore it and move to the next value. -- When you encounter a value > pivot, swap it with red index, and move red index to left, but check the value at that position again with these 3 points(the one which you had swapped for the > pivot value, ie the one that was previously at the red index) This might not make sense at first, but the way it works is that all values between green pointer and the one we are going to check, have been checked before, to be equal to pivot. Just try this for the example in the video... Its a pretty small improvement to reduce array accesses to exactly the size of the array, but its an improvement nonetheless. Sorry if my explanation was too confusing :)

[@BackToBackSWE]

nah u good

[@snlagr]

every superhero has a basement

[@BackToBackSWE]

tru

[@yipg2076]

I think the way you explained from 7:27 is not appropriate in the case like pivot number is 2 (Blue)

[@BackToBackSWE]

I dont remember this video too much

[@yipg2076]

@@BackToBackSWE k, don't mind. All your videos are very helpful for me to understand the problem well. Best Regards ;)

[@AffairWithGeo]

Am i late ?? in learning from you?

[@ayusharora2019]

Hey !! Can you please post the code for the same? in Java If possible

[@noa.leshem]

i just failed this question in a job interview 🤡 edit: nvm, bombed the question passed the interview

[@BackToBackSWE]

Congratulations on passing the interview 🎉

[@hawksawed]

4:45 if anyone is trying to see the 3 solutions

[@StanOliver1000]

What is so unusual about being in a basement??????

[@BackToBackSWE]

nothing

[@StanOliver1000]

@@BackToBackSWE Exactly

[@arowa.]

i literally thought that he will start by saying , hey yo my man's here rofl

[@BackToBackSWE]

what

[@anuragv400]

Should be Ez for Dutch peoples..

[@spk9434]

Awesome !

[@BackToBackSWE]

love.