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

[@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

[@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.

[@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

[@zarlorin3728]

this guy is more motivated than my prof in any ways

[@abhinavgupta1492]

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

[@BackToBackSWE]

sure

[@FrancisGabon]

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

[@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

[@sachitmohannayak4964]

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

[@BackToBackSWE]

hahaha nice, glad it did

[@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

[@69shrutivichare60]

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

[@jeezradz]

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

[@BackToBackSWE]

thanks and welcome

[@ritikkhatri]

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

[@BackToBackSWE]

Glad I could help!

[@colemanhoyt5437]

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

[@aribakodes5453]

you are a truly amazing teacher

[@BackToBackSWE]

thanks

[@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 😁

[@LalitYadav-vi1ul]

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

[@BackToBackSWE]

ok

[@OmniscientPotato]

Thank you for this excellent explanation!

[@BackToBackSWE]

thansk

[@deepaktiwari2847]

You were just FANTASTIC !!

[@BackToBackSWE]

thanks

[@vaibhavsingh755]

Great Explanation Sir😊

[@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; }

[@ananyapamde4514]

Really like your videos

[@PankajKumar-hz3oi]

thanks, brother, great explanation

[@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 ?

[@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 ;)

[@Ghungroo-Beats]

Great Explanation!

[@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

[@kumarc4853]

thank you

[@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

[@chengjiang7051]

Amazing solution

[@BackToBackSWE]

thx

[@jacobzhang840]

Great explanation!

[@BackToBackSWE]

thanks

[@YavinArba]

informative and engaging, thanks man

[@BackToBackSWE]

sure

[@nackyding]

Is the second example the bubble sort algorithm?

[@BackToBackSWE]

can you timestamp it?

[@pawehoowicki7940]

very nice!!

[@BackToBackSWE]

thx

[@xVermyy]

Bro, great explanation!

[@BackToBackSWE]

Thank you!

[@akashsrivastava8324]

Awesome !!!

[@sidhant4674]

Great work man!

[@BackToBackSWE]

thanks

[@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.

[@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

[@spk9434]

Awesome !

[@BackToBackSWE]

love.

[@AffairWithGeo]

Am i late ?? in learning from you?

[@ayusharora2019]

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

[@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..

[@Dyslexic_Neuron]

finally !!!

[@BackToBackSWE]

hi