I think you have to use 'else if' instead of if everywhere. Because for this ex 2,0,2,1,1,0 the output will come as 001212 Hope this will help you, or else if I am wrong , Please explain...Thank you
@@ajaychinni3148 nope we can maintain three variables count0 count1 count 2 and treverse array whenever 0 occurs increment count0 similarly for count1 and count2 and thn print ....O(N)
One idea can be (though not optimal )...iterating through array & calculating occurrences of 0s 1s 2s in 3 variables and placing them (0 1 2 ) accordingly into original array...
@@techdose4u But in a face to face round the interviewer might ask to optimize it further in a single pass as this solution takes 2 passes. In that case this Dutch Flag algorithm is the way to go.
this is better with no confusion Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s Traverse through the array and increase the count of c0 is the element is 0,increase the count of c1 is the element is 1 and increase the count of c2 is the element is 2 Now again traverse the array and replace first c0 elements with 0, next c1 elements with 1 and next c2 elements with 2.
@@techdose4u A question plz Tech dose. There r so many algo, i really don't know how is it possible for me to remember all of these, for example, this video. why m++ when arr[m] == 0 and 1... and also for other questions..... could u plz give me a little suggestion plz? super struggling here....ToT
This is not really an algo but just a hack :P You can do using counting the element frequencies :) You will get these ideas once have a lot of practice under your belt 😁 Ping me for any guidance on LinkedIn or Whatsapp or Instagram.
Nice explanation! Just a quick note, I think the code should be if( ... ) else if ( ... ) else if ( ... ) instead the if (...) if (...) if (...). I'm doing the "Sort Colors" problem from leetcode and I needed to change that
if you want to decrease the runtime, don't put 'else if(a[m]==1)' instead put this case in 'else block'. I guess, he was trying to keep the runtime low that why he put only if block but that was incorrect.
My explanation style was slightly different earlier but later I focussed more on intuition. So maybe you might different kind of approaches to my explanation from an old video compared to the ones I explained in past 4 months. But still I hope you can understand why we took the approach 😅 I evolved my style over time.
Thanks for the video, there are some cases which won't work as the terminating conditions are incorrect. Within the loop, we are incrementing pointers which may go out of bounds or may lead to inconsistent results (as Pratik24 mentioned), below will work. while(m
I think we don't need to swap if we are getting 1 because if we fix two element i.e 0 and 2 then 1 will be automatically fixed in between , so we can reduce work
if you want a solution with complexity O(n) then you can also do like this... 1st find all 2's and put it in stack then find all 1's and put it in stack then find all 0's and put it in stack then pop all elements... your output is sorted... here we got (3n) traversal hence equivalent to O(n)... yeah but yours O(n) is better than mine O(n)
sir why in third step we havnot did m++ also? . is it because after swapping arr[h] with arr[m]... the current arr[m] can be 0 or 1 ... if its 1 we'll move forward else if its 0 we'll have to swap it with arr[l]; ??
Why not simply count 0s, 1s and 2s and then fill the array accordingly? I guess it will take two passes as opposed to one so the solution mentioned in the video is more efficient (though might not be scalable when instead of 2s, we have a higher max limit).
Java Code (Beats 100 %) class Solution { public void sortColors(int[] nums) { int n = nums.length ; int[] arr = new int[3] ; int element = 0 ; for(int i = 0 ; i < n ; i++){ element = nums[i] ; arr[element]++ ; } int count = 0 ; int k = 0 ; for(int i = 0 ; i 0){ nums[k] = i ; k++ ; count-- ; } } } }
This will not pass all the test cases - for eg. 1,0,1,2,2,1. as you are just incrementing when its 1, the resulting array will not be correctly sorted.
Awesome explaination, hey you have done a lot of good interview preparation videos. Its a reuqest can u make a repository type something where you can put your videos topicwise ( Graph, Tree,...) . It will help during preparing on a topic to check all imoprtant problems on that topic..
Much easier solution-Make a count array with elements (0,0,0) where 0th index is 0 count 1st index is 1st count 2nd index 2nd count.Traverse the given array in question once and keep updating the 0 array then rewrite the question array with appropriate counts of 0,1,2
i have a same solution with same approach but a test case of size 65754 gives an error in gfg idk why and the solution is working fine for the element of small array
sir can we use this technique whenever we required sorting in a problem,suppose there list of no in aaray,we have to sort it,then by using direct sorting can we use this process
No you cannot. This is a very specific technique. Just see the problem and try to think of algo accordingly. Don't take any technique for granted to always work.
Inplace means you don't use any extra space but manipulate the words or elements within its own space. I think you are confusing with something else. Read this: en.m.wikipedia.org/wiki/In-place_algorithm
The intuition is already clear from the dry run. Since you have just 3 different values, so you can sort them like a Dutch flag. The intuition was already clear i guess. Now the tricky thing was to sort in just O(N) instead of O(NlogN). So we used the 3 pointer technique which segregates those values. I hope it's clear now :)
To maintain order, one simple way is to copy and perform operation on a different array which will take O(N) time and I know you might have thought of this.
two line using Java lib function , but not O(n) :| Arrays.sort(arr); System.out.println(Arrays.toString(arr).replaceAll("\\]","").replaceAll(",",""). replaceAll("\\[",""));
Thank you, you explained it very well, quick n simple. Others are wasting time for around 20 min.
:)
Same here
Yes
I think you have to use 'else if' instead of if everywhere. Because for this ex 2,0,2,1,1,0 the output will come as 001212
Hope this will help you, or else if I am wrong , Please explain...Thank you
You are right.
Right. I got stuck there too. Thanks.
Yup
Yup
No bro u r perfectly right
It was the best video on entire youtube. I love your simplest explanation.
Very succinctly explained, I remember solving this problem in O(n) but solution was very messy, this is just clean and simple!. Thanks!
👍
Amazing explanation in such a less time👍👌
Nice explaination. We can solve this just counting number of 1's,2's and 0's .
Yes correct.
yes we can, but u will have to traverse the array two time once for counting next for replacing them
@@ajaychinni3148 yah
@@ajaychinni3148 nope we can maintain three variables count0 count1 count 2 and treverse array whenever 0 occurs increment count0 similarly for count1 and count2 and thn print ....O(N)
Actually thought that will be still O(N) time but space will not be linear. That catch is it should be linear in space too.
The easiest explanation I came across.
One idea can be (though not optimal )...iterating through array & calculating occurrences of 0s 1s 2s in 3 variables and placing them (0 1 2 ) accordingly into original array...
I have done it like that only, but then I thought that it was not the optimal way and so I came here.
That's a bucket sort or count sort approach with 2 - pass solution.
Another (simpler) approach would be counting zeros and ones. Then mutating the array accordingly, it'll also take O(n) time & constant space.
Yes right.
@@techdose4u But in a face to face round the interviewer might ask to optimize it further in a single pass as this solution takes 2 passes. In that case this Dutch Flag algorithm is the way to go.
Nice straight forward explanation.
simple and precise! thank you.
Thanks! Your solutions are really well explained and simple to understand.
Welcome 😊
Count Sort will also do this in O(3N) ie. Linear time O(N) but it's mentioned to do it in one-pass and 3N is actually 3 pass
At a time only one condition should be executed, so need to use else if / switch cases.
Btw explanation was good.
very good, helped me a day before my interview. thanks :)
this is better with no confusion
Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s
Traverse through the array and increase the count of c0 is the element is 0,increase the count of c1 is the element is 1 and increase the count of c2 is the element is 2
Now again traverse the array and replace first c0 elements with 0, next c1 elements with 1 and next c2 elements with 2.
👍
Great video! Concise and clear!
Thanks :)
You teach really good, I guess it should be else if instead of the if in the latter two conditions.
Thank you buddy! u made it very clear ! we love u !
Welcome ❤️
@@techdose4u A question plz Tech dose. There r so many algo, i really don't know how is it possible for me to remember all of these, for example, this video. why m++ when arr[m] == 0 and 1... and also for other questions.....
could u plz give me a little suggestion plz? super struggling here....ToT
This is not really an algo but just a hack :P You can do using counting the element frequencies :) You will get these ideas once have a lot of practice under your belt 😁 Ping me for any guidance on LinkedIn or Whatsapp or Instagram.
@@techdose4u Whatsapp number plz !!! thank you ToT
@@user-oy4kf5wr8l +91 8918633037
you give the best explanation FR
Nice explanation!
Just a quick note, I think the code should be
if( ... )
else if ( ... )
else if ( ... )
instead the
if (...)
if (...)
if (...).
I'm doing the "Sort Colors" problem from leetcode and I needed to change that
if you want to decrease the runtime, don't put 'else if(a[m]==1)' instead put this case in 'else block'. I guess, he was trying to keep the runtime low that why he put only if block but that was incorrect.
this code does not run for multiple test cases on geeksforgeeks platform.
Maybe the constraints are changed or else try to tweak the code a little in if else statements.
Hey , but you need to explain , how this idea comes into your mind , like how you analyse the problem and find this approach ?
My explanation style was slightly different earlier but later I focussed more on intuition. So maybe you might different kind of approaches to my explanation from an old video compared to the ones I explained in past 4 months. But still I hope you can understand why we took the approach 😅 I evolved my style over time.
@@techdose4u yes this video does'nt seems like TECH DOSE's its more of a gfg kind. We now expect more than just to explain code.
It is a typical Dutch National Flag Algo problem
@@babbarutkarsh7770 Bhai mat dekh fir. He is helping us for free and u have the guts to point out his mistakes !! Don't be a choosing beggar
@@sehejwahla5437 have you ever heard of 'constructive criticism' ? He is pointing out mistake to improve quality right!!!...
Thanks for the video, there are some cases which won't work as the terminating conditions are incorrect. Within the loop, we are incrementing pointers which may go out of bounds or may lead to inconsistent results (as Pratik24 mentioned), below will work.
while(m
It would be also be Okay if we add else if insted if's
Thanks for the explanation buddy
No problem 👍
Nice explanation sir
Tq ❤
I think we don't need to swap if we are getting 1 because if we fix two element i.e 0 and 2 then 1 will be automatically fixed in between , so we can reduce work
Yes correct.
Thanks for sharing
Op explanation 🤯🤯🤯🤯😀
Thanks :)
class Solution
{
public void sortColors(int[] nums)
{
int i,j,k;
int len=nums.length;
i=0;
j=0;
k=len-1;
while(j
short and effective one
nice and fast explanation . liked it bhai.
Thanks :)
So well explained 😄😄
Thanks
Thanks found your explanation intutive !
Nice :)
Very nicely explained . good job
Thanks :)
Awesome explanation
Thanks :)
Nice explanation...It helped alot.
Thank you
Welcome :)
if you want a solution with complexity O(n) then you can also do like this...
1st find all 2's and put it in stack then
find all 1's and put it in stack then
find all 0's and put it in stack then pop all elements... your output is sorted...
here we got (3n) traversal hence equivalent to O(n)...
yeah but yours O(n) is better than mine O(n)
Yes... And also your technique is taking O(3n) extra space. But the technique in video is for O(1) space.
Another apporach is simply count 0's 1's and print it. For 2's len-0's-1's but the solution in video was algorithmic
We can also use hashing
👍🏼
there are some changes in the solution
correct solution :
if(a[m] ==2)
--h;
in video :
if(a[m] ==2)
h--;
Very Nice explanation sir..
Thanks :)
Thanks bro !! Ur punjabi fan
Welcome paji
Nice Explanation.
Thanks
sir why in third step we havnot did m++ also? . is it because after swapping arr[h] with arr[m]... the current arr[m] can be 0 or 1 ... if its 1 we'll move forward else if its 0 we'll have to swap it with arr[l]; ??
Leetcode 75 Sort colors
Great man 👌
If we knows that their is only 0,1,2 element. then why not just count frq. Of those 3 and fill the array it's also takes O(n) time and O(1) space.
But that will take 2 pass of array. You might be required to solve this in one pass. Like it's required on leetcode.
@@techdose4u thank you so so much!! This is really a smart solution!
I thought of this solution but missed m
This can be solved also with counting sort. And it can also be done in place just using 3 variables instead of array as usually
but than time complexity will be o(n) + o(n) = 2o(n)
but using this algo time complexity is just o(n)
@@zah1d_ali O(2n) is still the same as O(n), anyways, both are good solutions
Very nice explanation sir.
Nicely explained brother!!
Just keep count of number of 0,1 and 2...and fill the array with 0 ,1 and 2 Respectively
well... thats a 2 pass algo
Maintaining count of 0,1,2's and putting that many back in the array is far simpler
Nice solution :) keep going
Thanks :)
Why not simply count 0s, 1s and 2s and then fill the array accordingly? I guess it will take two passes as opposed to one so the solution mentioned in the video is more efficient (though might not be scalable when instead of 2s, we have a higher max limit).
Yea, but making use of the constraints is a good thing :)
Nice explanation sir.......
Thanks
very well explained😁
Thanks
Thanks
Really helpful
Thanks
What is the difference if we write len(nums) or len(nums)-1? In 2nd it indicates starting index is 0 then what about len(nums) ?
If you wanna access array index then we use len(nums)-1. If you do len(nums) then you need to explicitly subtract. Anyone is good and works fine :)
USE ELSE IF , other wise the output will be wrong , for such like cases 2 2 1 1 2 1 0 0 1 2 2
y is that happening can u explain
Java Code (Beats 100 %)
class Solution {
public void sortColors(int[] nums) {
int n = nums.length ;
int[] arr = new int[3] ;
int element = 0 ;
for(int i = 0 ; i < n ; i++){
element = nums[i] ;
arr[element]++ ;
}
int count = 0 ;
int k = 0 ;
for(int i = 0 ; i 0){
nums[k] = i ;
k++ ;
count-- ;
}
}
}
}
Awesome!
Thanks :)
why don’t we just count 0s ,1s and 2s.. Generate new arr and return
O(2N)
Doing it inplace and one traversal :)
Awesome ❤️
Thanks
Understood.
This will not pass all the test cases - for eg. 1,0,1,2,2,1. as you are just incrementing when its 1, the resulting array will not be correctly sorted.
Awesome explaination, hey you have done a lot of good interview preparation videos. Its a reuqest can u make a repository type something where you can put your videos topicwise ( Graph, Tree,...) . It will help during preparing on a topic to check all imoprtant problems on that topic..
I am currently working on my own website. It will be up in around a couple of months. You can find everything well organized there :)
@@techdose4u waiting
@@techdose4u
You are doing really an amazing work :)
Thanks a lot.
@@techdose4u is the website ready? would love to take a look
@@moulikasunesh2834 it's ready. Currently organizing the content.
Awesome
love youuu broo
Much easier solution-Make a count array with elements (0,0,0) where 0th index is 0 count 1st index is 1st count 2nd index 2nd count.Traverse the given array in question once and keep updating the 0 array then rewrite the question array with appropriate counts of 0,1,2
This is using 2 traversals. You could have done in 1 traversal by following the swapping method.
the interviewer will kick you out of the interview if you say this
@@llawliet1750 it's a solution not the best but ok ,O(2n) approximates to O(n)
instead of a[m]==2 is should be else{} other wise some case will fail for 2 2 1 1 2 1 0 0 1 2 2 and many more
perfect 👌
Thanks :)
ALL THREE if statement doesn't work beacause 3 if condition can be true simultaneously.
nice explanation
Thanks :)
//those who are getting any problem with the mentioned code on video can run this code:
int left = 0, right = a.length -1;
for(int i=0;i
👍
This solution will not work if we do not have 1 in the list, because m will never increased.
But the question itself said array of 0s 1s and 2s
i have a same solution with same approach but a test case of size 65754 gives an error in gfg idk why and the solution is working fine for the element of small array
yes bro, mine too. i dont understand whats the problem since it is returning 00000000000000.......like gfgs output
Can anyone answer our question
sir can we use this technique whenever we required sorting in a problem,suppose there list of no in aaray,we have to sort it,then by using direct sorting can we use this process
No you cannot. This is a very specific technique. Just see the problem and try to think of algo accordingly. Don't take any technique for granted to always work.
i think in while condition
the condition should be
while(mid while(mid
this condition is right mid
Counting sort can also solve this in O(n) since range of nums[i] is constant :)
yeah but that will take two passes and this algo does it only in single pass :)
Can we achieve the solution using low = 0 , mid = n-1 and high = n -1 ?
Thanks a lot
nice explanation .. but it's not in-place .. the ordering of 2's are changed ... does anybody know any in-place way of doing it .
Inplace means you don't use any extra space but manipulate the words or elements within its own space. I think you are confusing with something else. Read this: en.m.wikipedia.org/wiki/In-place_algorithm
yeah , you are right .. what i wanted to say ..that it's not stable .. i mean the ordering differs from the original array .
@@AruneshSrivastava of course the ordering will change you are sorting it lol
what is this algorithm called?
dutch national flag maybe :)
Why you didn't run the code in java...and where I can get code
I can only do one language. The main focus is to explain the logic. You can get code on internet or geeksforgeeks. See comments as well.
How do you come up with approaches, is it because of practice ?
Yea.
The same code is written in gfg but nice explanation bro..
@@DhavalBirade yep
Why not simply count the number of 0's 1's and 2's and then fill the array?
Just a 1 traversal thing ;)
@@techdose4u ok XD
In that way , ur solution will not follow the condition 'single pass'
U should have explained the intuition. Instead, You just dry run the solution. Not much beneficial.
The intuition is already clear from the dry run. Since you have just 3 different values, so you can sort them like a Dutch flag. The intuition was already clear i guess. Now the tricky thing was to sort in just O(N) instead of O(NlogN). So we used the 3 pointer technique which segregates those values. I hope it's clear now :)
not working for 2,0,1
Why not just count the 0s 1 2s and place them in array?
You can do that too in 2 traversals.
@@techdose4u yeah.. so this approach was more related to 1 traversal.. got it..
@@utkarshgupta2909 yea. Just for interview sake 😅
it can b solved using multiset in logn time
How? I don't think you can solve below O(N).
@@techdose4u i solved this
int n;
cin>>n;
int a[n];
multiset s;
for(int i=0;i>a[i];
s.insert(a[i]);
}
for(auto it=s.begin();it!=s.end();it++)
{
cout
@@neghatnazir1668 The question is to sort, not to print the sort form of given array. You have to modify the array
what is the intuition behind this?
What software do you use?
WHICH SOFTWARE DID YOU USE
how can we modify it if we want a stable sort?
To maintain order, one simple way is to copy and perform operation on a different array which will take O(N) time and I know you might have thought of this.
please clarify your approach.
One approach may be to avoid swapping if both the elements are same and update indexes accordingly.
send this code please
Dutch algorithm
Correct :)
this explaination coould be more better and clear, next time while making video ensure that you will work on that
Can we name this method as Indian Flag Method??
Yes you can :P
Good idea
two line using Java lib function , but not O(n) :|
Arrays.sort(arr);
System.out.println(Arrays.toString(arr).replaceAll("\\]","").replaceAll(",","").
replaceAll("\\[",""));