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
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
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.
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.
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).
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.
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
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
The only video that explained this clearly to me. Thank you!
1:14 Not gonna lie, Thought Thanos snapped in the first half
Really a detailed explanation that makes more sense. Thank you so Much Sir
Thankyou Sir, best explanation on RUclips :)
awesome explaination !!!!!!!! love the clarity of ur approach and visual analysis.
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.
best channel on yt to learn and improve skills from basics
very nice and clean explaned, thanks!
A very great and detailed explanation🤝, you make learning fun👏
Amazing content! Thanks for the algorithm videos. It has helped me a lot.
Thank you for the video that clearly explains how to segregate different value elements,
Good video and explanation. The first 5 mins are sufficient if you already have some grip on algorithms
Best Explaination on RUclips
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
How easy you made this problem... Wow!!!
Thanks a lot
awesome explanation. easy to understand
Good Explanation. Very easy to understand thanks a lot for making this video.
thank you for the very clear (and concise!) explanation
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
Very nice explanation
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.
Best explaination so far
Please keep them coming!!
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.
Thank you, your videos are very helpful!!! Keep going
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
very easy explanation..Nice
Useful for lot of people. Keep going
Well explained. Thanks a lot.
Glad it was helpful!
very impressive way of explaining algorithm !!
greatly explained. thanku sir
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.
Nicely explained
Thank you! I finally understand.
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).
Thank You sir !!
could the while condition be changed to while(mid
nice job, do you have the verification video of this? pre and post condition and loop invariants?
nicely explained! thanks
Good explanation
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.
Thankyou sir 🙏
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.
Thanks man..clear explanation..
Amazing sir. Keeping making such vids
This is related to leetcode problem 75.
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 sir 🖤
Sir please make separate playlist for all the topics..
Thank you. Very nice explanation
Thanks for sharing
Thank You Sir.
Thank you so much sir
very good explanation
very nice explanation
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
swap part i m not able to understand like how we can shift from case 0 to case 1,2
Thank You Sir
awesome sir ji u r gr8.
I wish I had taken your lectures before
Hi, Can you make video for median of two sorted array or median of stream?
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.
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 ,
you got new suscriber
Can you show this for 0,1,2,0,1,2 ??? I think this will fail.
and even for [1,2,0]
King of Algorithm's!
very useful thanks
amazing
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
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.
thankgod he is there :) saviour
Thank You
@ 5:30 look at the Flicka Da Wrist
thanks
This wont work for {0,1,2,1,2} because we arent finding the crct values of low,mid and high initially.
It works
Godly
sir your code is not working can any one provide source code ??
sir vector pairs , DSU,
nice
Whether this algorithim is in place?
no, it is a kind of quicksort algo
💞💞❤❤
but counting will also take O(n)
sir i need your github link
print(arr.sort())
The only question i have is.......
Where on earth will you ever use this.....???!!
The place where you got to know this algo!
Just sort the array in ascending order......that's it
very slow...
sir your code is not working can any one provide source code ??