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.
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.
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.
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
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.
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
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.
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
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.
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.
@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.
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..
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.
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).
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)
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 ,
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.
Khyade sir is the BEST
The only video that explained this clearly to me. Thank you!
Thank you for demonstrating all the detail and steps many algorithm books skip or leave exercises to readers.
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
1:14 Not gonna lie, Thought Thanos snapped in the first half
Thankyou Sir, best explanation on RUclips :)
best channel on yt to learn and improve skills from basics
Really a detailed explanation that makes more sense. Thank you so Much Sir
awesome explaination !!!!!!!! love the clarity of ur approach and visual analysis.
Best Explaination on RUclips
very nice and clean explaned, thanks!
Amazing content! Thanks for the algorithm videos. It has helped me a lot.
A very great and detailed explanation🤝, you make learning fun👏
Thank you for the video that clearly explains how to segregate different value elements,
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.
counting method takes two traversals while this algorithm takes only one traversal
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.
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.
Good Explanation. Very easy to understand thanks a lot for making this video.
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
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.
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
thank you for the very clear (and concise!) explanation
awesome explanation. easy to understand
Thank you, your videos are very helpful!!! Keep going
Good video and explanation. The first 5 mins are sufficient if you already have some grip on algorithms
How easy you made this problem... Wow!!!
Thanks a lot
Best explaination so far
Thank you! I finally understand.
Please keep them coming!!
Well explained. Thanks a lot.
Glad it was helpful!
Very nice explanation
very easy explanation..Nice
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.
Useful for lot of people. Keep going
very impressive way of explaining algorithm !!
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
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.
Thankyou sir 🙏
could the while condition be changed to while(mid
Thanks man..clear explanation..
Thank You sir !!
Nicely explained
nice explanation but counting 1 2 3 can also be done in 0(n) so how this one more efficient?
efficiency here is that it does all that in the single pass.
@@sumansaurabh8105 oh u meant we can't calculate 1,2,0 count in one pass?
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.
@@sumansaurabh8105 satisfied thanks
@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.
greatly explained. thanku sir
Amazing sir. Keeping making such vids
Thank you sir 🖤
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
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..
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.
Counting the number of 0s, 1s, and 2s and then replacing the array is also O(n). However, it is not in-place.
It will also take 2 pass to sort the array. Dutch national flag will sort the array in 1 pass.
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).
nicely explained! thanks
Thank you. Very nice explanation
Use Counting sorting for this problem that would be helpful with O(1) space complexity
But in interview they say not to use that approach and do swapping based
Good explanation
Anyone knows how to find the algorithm if we decide to have Four numbers instead of 3. Would we use the above approach
Thank you so much sir
Thank You Sir.
This is related to leetcode problem 75.
Thanks for sharing
Sir please make separate playlist for all the topics..
King of Algorithm's!
Thank You Sir
I wish I had taken your lectures before
swap part i m not able to understand like how we can shift from case 0 to case 1,2
Why didnt we use counting sort for this problem? Counting sort takes O(n) Time complexity. It uses extra space though.
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)
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.
Sir can we use sorting alogrithm
I would be very easy than any other method
in the interviews they want us to solve it without sorting, so this algorithm is used.
you got new suscriber
very good explanation
awesome sir ji u r gr8.
nice job, do you have the verification video of this? pre and post condition and loop invariants?
very nice explanation
Can you show this for 0,1,2,0,1,2 ??? I think this will fail.
and even for [1,2,0]
Hi, Can you make video for median of two sorted array or median of stream?
very useful thanks
thankgod he is there :) saviour
amazing
💞💞❤❤
Very good explanation, but naming of mid is confusing, Why don't you rename mid to tracker / pointer/currentIndex.
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 ,
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]
Problem : code logic is not correct
solution: Add mid
@ 5:30 look at the Flicka Da Wrist
Thank You
Godly
thanks
sir your code is not working can any one provide source code ??
nice
sir vector pairs , DSU,
but counting will also take O(n)
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.
Whether this algorithim is in place?
no, it is a kind of quicksort algo
This wont work for {0,1,2,1,2} because we arent finding the crct values of low,mid and high initially.
It works
print(arr.sort())
sir i need your github link
Just sort the array in ascending order......that's it
very slow...
The only question i have is.......
Where on earth will you ever use this.....???!!
The place where you got to know this algo!
sir your code is not working can any one provide source code ??