Segregate 0's, 1's and 2's together in an array[O(n)](Dutch National Flag Problem)

[@dongiveajack]

Khyade sir is the BEST

[@lien-chinwei4815]

Thank you for demonstrating all the detail and steps many algorithm books skip or leave exercises to readers.

[@sjwang3892]

The only video that explained this clearly to me. Thank you!

[@arunm619]

1:14 Not gonna lie, Thought Thanos snapped in the first half

[@ashishmishra8082]

You explained it as a specific example of segregating 0,1 and 2 but it helped me to understand 3 way partition of Quicksort. Thanks sir

[@jainmanan9182]

Thankyou Sir, best explanation on KZbin :)

[@RajaRam-fv1mm]

Really a detailed explanation that makes more sense. Thank you so Much Sir

[@Vishal-nc8ju]

best channel on yt to learn and improve skills from basics

[@praveenchouhan6388]

awesome explaination !!!!!!!! love the clarity of ur approach and visual analysis.

[@skubydubydu]

Counting method also takes O(n) time. It is also taking least time. The reason the swapping method is asked in interviews is because in real scenarios the actual data set is not going to contain just simple numbers. It will be made of records which need to be sorted based on one of the properties of the records.

[@GurpreetSingh-yy5fn]

counting method takes two traversals while this algorithm takes only one traversal

[@udaykadam5455]

Doesn't matter even if the data is in the string format. You can still count the number of occurrences. It's just that, interviewer will ask for another solution. Combination of double pointer approach along with hoare partion algo can solve this problem within linear time.

[@AvinashKumar-ps8wl]

Best Explaination on KZbin

[@abhisheksarkar_neo]

As proposed at the start of the video, counting is also a way to do it and that will also take O(n) time. The reason we cannot do that is because, it will not work in cases where you have any set of numbers, not just 0, 1 and 2 and you want to partition the numbers in 3 buckets

[@sravanvedala7811]

well even with this approach also, you need as many buckets as that of your number groups. For example if you have 0 to 5 numbers repeated in an array, then you need to modify this algorithm to address grouping of 0 to5 numbers in which you case you end up having 6 buckets even with this algorithm. This won't work out of the box if your array has numbers other than 0,1 and 2. However caveat with just counting is, you need another array.

[@spetsnaz_2]

If you do it by counting, then it will take 2 passes to complete the program, but this algo will do the job in a single pass. And this algo is only made for this kind of problems...if we have more no. of distinct elements, why not to use other sorting techniques :P

[@krishnataramanandhar581]

Thank you for the video that clearly explains how to segregate different value elements,

[@ThinkProgramming-Hub]

A very great and detailed explanation🤝, you make learning fun👏

[@niklasschulte1690]

very nice and clean explaned, thanks!

[@JayDonga]

You demonstrated algorithm and it works really well. However if someone has never encountered this solution before and they get this problem in interview, in that case how to develop this algorithm from scratch? Appreciate your inputs.

[@ankitchawla8487]

Good Explanation. Very easy to understand thanks a lot for making this video.

[@adityagunda2122]

awesome explanation. easy to understand

[@aishwaryasingh246]

Amazing content! Thanks for the algorithm videos. It has helped me a lot.

[@Akash-Bisariya]

How easy you made this problem... Wow!!!

[@vivekanandkhyade]

Thanks a lot

[@Badatbackflips]

thank you for the very clear (and concise!) explanation

[@angitd3766]

Best explaination so far

[@minirasamedova648]

Please keep them coming!!

[@CASHTECH1234]

Good video and explanation. The first 5 mins are sufficient if you already have some grip on algorithms

[@hiteshusingh8571]

Very nice explanation

[@chaoschao9432]

This is related to leetcode problem 75.

[@rahulchandrabhan]

very easy explanation..Nice

[@DurgaShiva7574]

could the while condition be changed to while(mid

[@subrinasirajee530]

Well explained. Thanks a lot.

[@vivekanandkhyade]

Glad it was helpful!

[@kewtomrao]

So mid travels through the array and when 1 is encountered,we allow it to be in its place but if its 0 we swap it to the left end of 1 ie with the low index and inc low by 1 since the 0 has been placed on the right.But if its greater than 1 then we swap it with the high index ie to the right of 1 and dec high since the 2 has already been put to the end.

[@amishapurswani9957]

greatly explained. thanku sir

[@sasmitasahoo1161]

Nicely explained

[@Bakepichai]

Useful for lot of people. Keep going

[@prnk139]

very impressive way of explaining algorithm !!

[@colettecampbell1528]

Thank you! I finally understand.

[@rajatmishra3572]

Thank You sir !!

[@deepakdas4224]

Use Counting sorting for this problem that would be helpful with O(1) space complexity

[@ThotaMadhuSudhanRao]

But in interview they say not to use that approach and do swapping based

[@DurgaShiva7574]

also Vivekanad Sir...as you said that u can make videos as per ur subscribers request ..so please explain the theory then programming/code of Edges and graphs...as every company is asking it..and i am totally blank for it..hoping to hear from u soon

[@anshulsaini7440]

Thankyou sir 🙏

[@sholihatulrichas9414]

Thank you, your videos are very helpful!!! Keep going

[@sukritkapil9816]

nicely explained! thanks

[@auritroghoshal8469]

Thank You Sir.

[@neharikakhera6411]

Thanks for sharing

[@adityapaithon6499]

Good explanation

[@sentinel-y8l]

When a[mid] == 2, a[high], besides being 0 or 1 can also be 2, which would need to be moved (like the 0 you mentioned). You simply know nothing about a[high] because you never processed that value before, as opposed to a[low] (which was processed before, so it can only be 0 - first iteration, or 1 all other iterations). This is due to you starting mid iterations from left to right.

[@Anubis10110]

Thanks man..clear explanation..

[@davidotewa6411]

Anyone knows how to find the algorithm if we decide to have Four numbers instead of 3. Would we use the above approach

[@letstalk8670]

Sir please make separate playlist for all the topics..

[@MrMarkgyuro]

King of Algorithm's!

[@shailshah9021]

Counting the number of 0s, 1s, and 2s and then replacing the array is also O(n). However, it is not in-place.

[@abhimanyusharma3741]

It will also take 2 pass to sort the array. Dutch national flag will sort the array in 1 pass.

[@gamma_v1]

It's actually in-place (see the definition of in-place: en.wikipedia.org/wiki/In-place_algorithm). The reason this method is not acceptable for this problem is that by definition of the problem you are only allowed to swap elements (see the definition of Dutch National Flag Problem in Wikipedia).

[@shofiyabootwala2094]

Thank You Sir

[@shreyanaik6062]

Thank you so much sir

[@TechieAlpha]

Thank you sir 🖤

[@farazahmed6043]

Amazing sir. Keeping making such vids

[@deepakdubey519]

I wish I had taken your lectures before

[@anjurawat9274]

nice explanation but counting 1 2 3 can also be done in 0(n) so how this one more efficient?

[@sumansaurabh8105]

efficiency here is that it does all that in the single pass.

[@anjurawat9274]

@@sumansaurabh8105 oh u meant we can't calculate 1,2,0 count in one pass?

[@sumansaurabh8105]

You can but then in one pass you will count all the 0,1 and 2s and then you will probably make another array to populate those or go one more pass to populate the original array with 0,1 and 2. The challenge here is you have to do in memory without using extra space and in one pass. Hence this solution. I would recommend you to go too leetcode and read the problem description.

[@anjurawat9274]

@@sumansaurabh8105 satisfied thanks

[@nikhilm4290]

@suman once we count the number of 0's,1's and 2's why do we place in an extra array. We can just override the elements in given array since we know the count of each. I understand it takes O(2n)=>O(n) but as long as the interviewer is happy we can go with count solution. It is always not necessary to give text book solutions and it is a very natural way to think about the count initially even before you propose this textbook solution. I hope you agree with this.

[@alexanderpeles81]

Thank you. Very nice explanation

[@coderajput1816]

very good explanation

[@ah62mousavi]

nice job, do you have the verification video of this? pre and post condition and loop invariants?

[@dewdropk-dl5tv]

very nice explanation

[@infotainment7123]

you got new suscriber

[@lokeshagarwal6219]

swap part i m not able to understand like how we can shift from case 0 to case 1,2

[@babu123456781]

Why didnt we use counting sort for this problem? Counting sort takes O(n) Time complexity. It uses extra space though.

[@simranjeetsingh6002]

In counting sort you need to traverse the array twice (first time for counting and second time for putting) ,so its time complexity is O(2n) but in this one only once you have to traverse so its purely O(n)

[@gurmeetchawla8362]

simran O(2n) is also O(n) only, I am sure you know that, but I am not trying to justify using of count sort for this problem.

[@adarshpanigrahi7777]

Sir can we use sorting alogrithm I would be very easy than any other method

[@GurpreetSingh-yy5fn]

in the interviews they want us to solve it without sorting, so this algorithm is used.

[@mayankaggarwal2937]

i have an question .. why you don't just sorted the elements using merge sort.. because for worst case also..its complexity is o(nlogn)..and in this video you are getting o(n) complexity.i think merge sort would be a very nycc option .can you please explain..

[@ankurshah3112]

You can do it in O(n)via countSort in 2 pass,but this is trying to do it in one pass. Question has this constraint. If somebody asks you to do it in 1 pass, this is how you would solve it.

[@bigray712]

amazing

[@AdityaKumar-ws5pv]

awesome sir ji u r gr8.

[@sourovroy7951]

The Solution is buggy. It will not pass [1,2,0]. Try this one: void sort(vector& nums) { int left=0,mid=0,right=nums.size()-1; while(mid

[@SoumikNandi]

Godly

[@rushi901]

Hi, Can you make video for median of two sorted array or median of stream?

[@lazy_engineer]

very useful thanks

[@Ram-kv1xp]

@ 5:30 look at the Flicka Da Wrist

[@dasabhishek0790]

Can you show this for 0,1,2,0,1,2 ??? I think this will fail.

[@monalisadas9062]

and even for [1,2,0]

[@prajitbanerjee8226]

nice

[@KnowledgeActionWords]

thanks

[@rahulkhandelwal46578]

Thank You

[@vineetktripathi]

Very good explanation, but naming of mid is confusing, Why don't you rename mid to tracker / pointer/currentIndex.

[@vaibhavrbs]

I was thinking the same, however if you think about it, calling it mid makes more sense as mid_value_index as it stays with 1, similarly with high_value_index as it stays with 2 and same case with low_value_index as it stays with 0 ,

[@payalsagar1808]

thankgod he is there :) saviour

[@good114]

💞💞❤❤

[@sachinbhalla14]

sir your code is not working can any one provide source code ??

[@chaoschao9432]

Whether this algorithim is in place?

[@yatheeshareddy3661]

no, it is a kind of quicksort algo

[@rishabhbisht7014]

This didn't work for me when passed an array = [1,0,1,0,1,0,1,0,2,0,2,0,2,0,2,0,2,1,0,1,0,1,0]

[@arnavrastogi8473]

Problem : code logic is not correct solution: Add mid

[@sanjaysingh5007]

sir vector pairs , DSU,

[@sumanthv2046]

This wont work for {0,1,2,1,2} because we arent finding the crct values of low,mid and high initially.

[@pratikparikh8027]

It works

[@chandangarg1328]

but counting will also take O(n)

[@kansiram5340]

sir i need your github link

[@abhishektiwari5932]

print(arr.sort())

[@SIG442]

Yet your own flag, India I take it, is based up on the Dutch flag like so many other nations. That would mean that your own flag has a problem as well ;) Aside from that, I tried to follow what you were saying. But I have no clue still what you are trying to tell with this. Please do explain. I can't say I had any useful education at school, along side that I was the target for pretty much everyone. So learning wasn't really my primary thing to do in my early years. Yet I seem to be smart enough to follow very advanced things in many cases, with the right explanation. I like to learn and understand more.

[@tusharbhart4105]

Just sort the array in ascending order......that's it

[@Matkartik-yz4vs]

very slow...

[@stholy32]

The only question i have is....... Where on earth will you ever use this.....???!!

[@spetsnaz_2]

The place where you got to know this algo!

[@sachinbhalla14]

sir your code is not working can any one provide source code ??