Thank you, you explained it very well, quick n simple. Others are wasting time for around 20 min.
@techdose4u5 жыл бұрын
:)
@abhilashpatel30364 жыл бұрын
Same here
@rpw2k232 жыл бұрын
Yes
@dineshrajendran71282 жыл бұрын
Thanks! Your solutions are really well explained and simple to understand.
@techdose4u2 жыл бұрын
Welcome 😊
@zubairzafar480 Жыл бұрын
It was the best video on entire youtube. I love your simplest explanation.
@shubhamhire93902 жыл бұрын
Amazing explanation in such a less time👍👌
@pratik23194 жыл бұрын
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
@cloud154874 жыл бұрын
You are right.
@akshayshahi2964 жыл бұрын
Right. I got stuck there too. Thanks.
@pratyushbhatt17124 жыл бұрын
Yup
@preritcreed15264 жыл бұрын
Yup
@sunnykakrani78304 жыл бұрын
No bro u r perfectly right
@_overide4 жыл бұрын
Very succinctly explained, I remember solving this problem in O(n) but solution was very messy, this is just clean and simple!. Thanks!
@techdose4u4 жыл бұрын
👍
@Mazhar_Khan018 ай бұрын
The easiest explanation I came across.
@kshitijshirole22103 жыл бұрын
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...
@choudharyhimanshu41342 жыл бұрын
I have done it like that only, but then I thought that it was not the optimal way and so I came here.
@suraj809211 ай бұрын
That's a bucket sort or count sort approach with 2 - pass solution.
@adityaanand4749 Жыл бұрын
Nice straight forward explanation.
@sanskrutikapade42382 жыл бұрын
very good, helped me a day before my interview. thanks :)
@kunalkheeva2 жыл бұрын
simple and precise! thank you.
@666Imaginative2 жыл бұрын
you give the best explanation FR
@RajKumar-qv7ci4 жыл бұрын
Nice explaination. We can solve this just counting number of 1's,2's and 0's .
@techdose4u4 жыл бұрын
Yes correct.
@ajaychinni31484 жыл бұрын
yes we can, but u will have to traverse the array two time once for counting next for replacing them
@Voice_Of_Thoughts4 жыл бұрын
@@ajaychinni3148 yah
@neghatnazir16684 жыл бұрын
@@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)
@ssahoo19854 жыл бұрын
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.
@ankitupadhyay9183 жыл бұрын
Op explanation 🤯🤯🤯🤯😀
@techdose4u3 жыл бұрын
Thanks :)
@大盗江南3 жыл бұрын
Thank you buddy! u made it very clear ! we love u !
@techdose4u3 жыл бұрын
Welcome ❤️
@大盗江南3 жыл бұрын
@@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
@techdose4u3 жыл бұрын
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.
@大盗江南3 жыл бұрын
@@techdose4u Whatsapp number plz !!! thank you ToT
@techdose4u3 жыл бұрын
@@大盗江南 +91 8918633037
@mananvarma59444 жыл бұрын
Another (simpler) approach would be counting zeros and ones. Then mutating the array accordingly, it'll also take O(n) time & constant space.
@techdose4u4 жыл бұрын
Yes right.
@mananvarma59444 жыл бұрын
@@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.
@jianingzhuang1044 жыл бұрын
Great video! Concise and clear!
@techdose4u4 жыл бұрын
Thanks :)
@gigachadkartik2 жыл бұрын
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
@pryansh_3 жыл бұрын
So well explained 😄😄
@techdose4u3 жыл бұрын
Thanks
@jaydeepmahajan65984 жыл бұрын
Hey , but you need to explain , how this idea comes into your mind , like how you analyse the problem and find this approach ?
@techdose4u4 жыл бұрын
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.
@babbarutkarsh77704 жыл бұрын
@@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.
@Shaillha4 жыл бұрын
It is a typical Dutch National Flag Algo problem
@sehejwahla54374 жыл бұрын
@@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
@varsha90944 жыл бұрын
@@sehejwahla5437 have you ever heard of 'constructive criticism' ? He is pointing out mistake to improve quality right!!!...
@chetanshrivastava37624 жыл бұрын
Very Nice explanation sir..
@techdose4u4 жыл бұрын
Thanks :)
@nishantsharma31004 жыл бұрын
nice and fast explanation . liked it bhai.
@techdose4u4 жыл бұрын
Thanks :)
@hemanthar83633 жыл бұрын
Nicely explained brother!!
@akankshakanjolia29694 жыл бұрын
Awesome explanation
@techdose4u4 жыл бұрын
Thanks :)
@nithinkumar92263 жыл бұрын
Nice explanation sir Tq ❤
@VipinChaudhary141195 жыл бұрын
Very nicely explained . good job
@techdose4u5 жыл бұрын
Thanks :)
@sehejwahla54374 жыл бұрын
Thanks bro !! Ur punjabi fan
@techdose4u4 жыл бұрын
Welcome paji
@harifrahman80544 жыл бұрын
Nice solution :) keep going
@techdose4u4 жыл бұрын
Thanks :)
@shivanshkaushal4203 жыл бұрын
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]; ??
@paragroy53594 жыл бұрын
Nice explanation sir.......
@techdose4u4 жыл бұрын
Thanks
@shadanzahid45944 жыл бұрын
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
@techdose4u4 жыл бұрын
Yes correct.
@poojaupadhyay63644 жыл бұрын
this code does not run for multiple test cases on geeksforgeeks platform.
@techdose4u4 жыл бұрын
Maybe the constraints are changed or else try to tweak the code a little in if else statements.
@sambeetnayak10023 жыл бұрын
At a time only one condition should be executed, so need to use else if / switch cases. Btw explanation was good.
@saruncse853 жыл бұрын
Nice Explanation.
@techdose4u3 жыл бұрын
Thanks
@DonTaldo3 жыл бұрын
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
@iaashu98x2 жыл бұрын
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.
@Margdarshak_13 жыл бұрын
We can also use hashing
@techdose4u3 жыл бұрын
👍🏼
@lalitkumarnaidu14 жыл бұрын
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
@alstrarame33874 жыл бұрын
It would be also be Okay if we add else if insted if's
@amankumarjha94383 жыл бұрын
Very nice explanation sir.
@myriad1703 Жыл бұрын
Thanks for the explanation buddy
@techdose4u Жыл бұрын
No problem 👍
@arkadeepsen67314 жыл бұрын
You teach really good, I guess it should be else if instead of the if in the latter two conditions.
@sagarbora77683 жыл бұрын
Thanks found your explanation intutive !
@techdose4u3 жыл бұрын
Nice :)
@patilsoham4 жыл бұрын
Nice explanation...It helped alot. Thank you
@techdose4u4 жыл бұрын
Welcome :)
@dmsohel13354 жыл бұрын
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.
@techdose4u4 жыл бұрын
👍
@sangramkapre4 жыл бұрын
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).
@techdose4u4 жыл бұрын
Yea, but making use of the constraints is a good thing :)
@zaltech4 жыл бұрын
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.
@techdose4u4 жыл бұрын
But that will take 2 pass of array. You might be required to solve this in one pass. Like it's required on leetcode.
@Dizzydizzydizzy74 жыл бұрын
@@techdose4u thank you so so much!! This is really a smart solution!
@bhanupratapsingh89824 жыл бұрын
very well explained😁
@techdose4u4 жыл бұрын
Thanks
@ManojKumar-hj7fh4 жыл бұрын
How do you come up with approaches, is it because of practice ?
@techdose4u4 жыл бұрын
Yea.
@DhavalBirade4 жыл бұрын
The same code is written in gfg but nice explanation bro..
@techdose4u4 жыл бұрын
@@DhavalBirade yep
@premhulikoppe14702 жыл бұрын
short and effective one
@AnasMourad3 жыл бұрын
What software do you use?
@nknidhi3213 жыл бұрын
Awesome ❤️
@techdose4u3 жыл бұрын
Thanks
@TheArbaaz-rn2tq4 жыл бұрын
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) ?
@techdose4u4 жыл бұрын
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 :)
@pabloarkadiusz46874 жыл бұрын
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
@zah1d_ali4 жыл бұрын
but than time complexity will be o(n) + o(n) = 2o(n) but using this algo time complexity is just o(n)
@AdrianGonzalezBlogs4 жыл бұрын
@@zah1d_ali O(2n) is still the same as O(n), anyways, both are good solutions
@saisriangajala83993 жыл бұрын
I thought of this solution but missed m
@rahuldey55646 ай бұрын
what is this algorithm called?
@techdose4u6 ай бұрын
dutch national flag maybe :)
@nandhagopalcs56083 жыл бұрын
Really helpful
@techdose4u3 жыл бұрын
Thanks
@karanhemdev53255 жыл бұрын
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)
@techdose4u5 жыл бұрын
Yes... And also your technique is taking O(3n) extra space. But the technique in video is for O(1) space.
@sivaganesh44894 жыл бұрын
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
@hirakmondal61743 жыл бұрын
Why not simply count the number of 0's 1's and 2's and then fill the array?
@techdose4u3 жыл бұрын
Just a 1 traversal thing ;)
@hirakmondal61743 жыл бұрын
@@techdose4u ok XD
@surendharv7952 жыл бұрын
In that way , ur solution will not follow the condition 'single pass'
@philosphize2 жыл бұрын
Thanks for sharing
@ravishankarsingh75124 жыл бұрын
Why you didn't run the code in java...and where I can get code
@techdose4u4 жыл бұрын
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.
@shaswatsingh4 жыл бұрын
WHICH SOFTWARE DID YOU USE
@yashnarang6373 жыл бұрын
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
@rosonerri-faithful3 жыл бұрын
yes bro, mine too. i dont understand whats the problem since it is returning 00000000000000.......like gfgs output
@yashnarang6373 жыл бұрын
Can anyone answer our question
@ShreyaSingh-vr9qi4 жыл бұрын
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..
@techdose4u4 жыл бұрын
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 :)
@karann60104 жыл бұрын
@@techdose4u waiting
@ritishdhiman264 жыл бұрын
@@techdose4u You are doing really an amazing work :) Thanks a lot.
@moulikasunesh28344 жыл бұрын
@@techdose4u is the website ready? would love to take a look
@techdose4u4 жыл бұрын
@@moulikasunesh2834 it's ready. Currently organizing the content.
@utkarshgupta29093 жыл бұрын
Why not just count the 0s 1 2s and place them in array?
@techdose4u3 жыл бұрын
You can do that too in 2 traversals.
@utkarshgupta29093 жыл бұрын
@@techdose4u yeah.. so this approach was more related to 1 traversal.. got it..
@techdose4u3 жыл бұрын
@@utkarshgupta2909 yea. Just for interview sake 😅
@rishurana96553 жыл бұрын
what is the intuition behind this?
@AruneshSrivastava5 жыл бұрын
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 .
@techdose4u5 жыл бұрын
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
@AruneshSrivastava5 жыл бұрын
yeah , you are right .. what i wanted to say ..that it's not stable .. i mean the ordering differs from the original array .
@BarkaDog4 жыл бұрын
@@AruneshSrivastava of course the ordering will change you are sorting it lol
@harshpatel13855 жыл бұрын
nice explanation
@techdose4u5 жыл бұрын
Thanks :)
@theofficialgauravsharma87313 жыл бұрын
Awesome!
@techdose4u3 жыл бұрын
Thanks :)
@hassaanistic Жыл бұрын
love youuu broo
@vikasrai49154 жыл бұрын
how can we modify it if we want a stable sort?
@techdose4u4 жыл бұрын
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.
@vikasrai49154 жыл бұрын
please clarify your approach. One approach may be to avoid swapping if both the elements are same and update indexes accordingly.
@chanpreetsingh0073 жыл бұрын
Just keep count of number of 0,1 and 2...and fill the array with 0 ,1 and 2 Respectively
@saiavinashduddupudi89752 жыл бұрын
well... thats a 2 pass algo
@CodeSuccessChronicle3 жыл бұрын
perfect 👌
@techdose4u3 жыл бұрын
Thanks :)
@SomnathDas-fg2qc4 жыл бұрын
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
@techdose4u4 жыл бұрын
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.
@vishalmane53533 жыл бұрын
there are some changes in the solution correct solution : if(a[m] ==2) --h; in video : if(a[m] ==2) h--;
@gsujithkumar14173 жыл бұрын
Maintaining count of 0,1,2's and putting that many back in the array is far simpler
@neghatnazir16684 жыл бұрын
it can b solved using multiset in logn time
@techdose4u4 жыл бұрын
How? I don't think you can solve below O(N).
@neghatnazir16684 жыл бұрын
@@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
@killadasatyaaditya59604 жыл бұрын
@@neghatnazir1668 The question is to sort, not to print the sort form of given array. You have to modify the array
@PriyanshuJain-w7r Жыл бұрын
not working for 2,0,1
@Voice_Of_Thoughts4 жыл бұрын
class Solution { public void sortColors(int[] nums) { int i,j,k; int len=nums.length; i=0; j=0; k=len-1; while(j
@YashCodesX3 жыл бұрын
why don’t we just count 0s ,1s and 2s.. Generate new arr and return O(2N)
@techdose4u3 жыл бұрын
Doing it inplace and one traversal :)
@aznstride43253 жыл бұрын
Counting sort can also solve this in O(n) since range of nums[i] is constant :)
@shubhamraj25 Жыл бұрын
yeah but that will take two passes and this algo does it only in single pass :)
@mwshubham3 жыл бұрын
Leetcode 75 Sort colors
@techdose4u3 жыл бұрын
Great man 👌
@nilaysheth32833 жыл бұрын
Can we achieve the solution using low = 0 , mid = n-1 and high = n -1 ?
@shubhamsonal58715 жыл бұрын
Awesome
@rakeshjaiswal27903 жыл бұрын
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.
@643kanavguleria94 жыл бұрын
i think in while condition the condition should be while(mid while(mid
@ojasvichaudhary87243 жыл бұрын
this condition is right mid
@tauros56513 жыл бұрын
Thanks a lot
@hari85684 жыл бұрын
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
@techdose4u4 жыл бұрын
This is using 2 traversals. You could have done in 1 traversal by following the swapping method.
@llawliet17502 жыл бұрын
the interviewer will kick you out of the interview if you say this
@hari85682 жыл бұрын
@@llawliet1750 it's a solution not the best but ok ,O(2n) approximates to O(n)
@AnkitMishra-mz4xt4 жыл бұрын
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
@dhanushiyer12414 жыл бұрын
y is that happening can u explain
@NarendraKumar-by6vv11 ай бұрын
ALL THREE if statement doesn't work beacause 3 if condition can be true simultaneously.
@ssahoo19854 жыл бұрын
This solution will not work if we do not have 1 in the list, because m will never increased.
@manisherukulla17794 жыл бұрын
But the question itself said array of 0s 1s and 2s
@MMNayem-dq4kd Жыл бұрын
Thanks
@neerajmahapatra52393 жыл бұрын
Understood.
@shubhamsingh47012 жыл бұрын
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
@ahmedatef41713 жыл бұрын
send this code please
@ankitraj41796 ай бұрын
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-- ; } } } }
@aksharkashyap4 жыл бұрын
//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
@techdose4u4 жыл бұрын
👍
@marriagedance86575 жыл бұрын
U should have explained the intuition. Instead, You just dry run the solution. Not much beneficial.
@techdose4u5 жыл бұрын
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 :)
@spetsnaz_25 жыл бұрын
Can we name this method as Indian Flag Method??
@techdose4u5 жыл бұрын
Yes you can :P
@sivaganesh44894 жыл бұрын
Good idea
@techconvos4 жыл бұрын
this explaination coould be more better and clear, next time while making video ensure that you will work on that
@AnkitSingh-zj2uc4 жыл бұрын
Dutch algorithm
@techdose4u4 жыл бұрын
Correct :)
@code_with_mathan4 жыл бұрын
two line using Java lib function , but not O(n) :| Arrays.sort(arr); System.out.println(Arrays.toString(arr).replaceAll("\\]","").replaceAll(",",""). replaceAll("\\[",""));