Please watch our new video on the same topic: • BS-24. Search in a 2D ... Check our Website: Note: • BS-24. Search in a 2D ...
Пікірлер: 305
@takeUforward4 жыл бұрын
Understood or not ? Drop a Yes or No :D .. . Check me out at Instagram: instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
@2501Lucky4 жыл бұрын
Yes, superb depth
@14Bishal4 жыл бұрын
Yes, all 3 solutions 👍 PS- please correct the problem link in the description, the unique paths problem link has got merged with this problem. leetcode.com/problems/unique-paths/leetcode.com/problems/majority-element-ii/
@sahilchoudhary14734 жыл бұрын
Yes
@priyanshiagrawal94274 жыл бұрын
amazing ...thanks a lot for providing such help...and please try to provide brute force code in every question ...it makes thing more clear ,there is no need to explain that but seeing the brute force makes it easier to go forward
@LegitGamer23453 жыл бұрын
In the recursive solution if i and j are set to 0 at start then how will I and j ever be greater than n and m respectively ? in the second if condition is it compulsory to write >= or can we just use ==
@sheikhaman62184 жыл бұрын
The way you teach is nothing but magic.. And you are 100 % coder and 200% magician... 💥😎❤
@AjeetKumar-ty8zs3 жыл бұрын
I got to understand recursion first time in my entire life. Thanks man!!!
@hrithikgarg03183 жыл бұрын
In 3rd approach we can take min (m, n) as r in Ncr method .I think this will helps to more optimze the code.
@Itskrmani2 жыл бұрын
for combinatorics solution , there may be the possiblity when ans become greator than or less than actual ans, due to conversion of int so we have to do it carefully. int uniquePaths(int m, int n) { int nn = m+n-2; int rr = min(m-1,n-1); double ans = 1; for(double i=1;i int(ans)+0.5){ return ceil(ans); } return int(ans); }
@Jack-mc7qe2 жыл бұрын
Remove that if condition just return (int)(ans+0.5)
@mohitratanpal272 жыл бұрын
what does 0.5 here mean
@Jack-mc7qe2 жыл бұрын
@@mohitratanpal27 there can only be 2 options, number can be between e,g 3-3.5 or 3.5-4 if 1st case then incremented by 0.5 will result in values less than 4 so int will take 3 only thats what is reqd and in 2nd case after incrementing by 0.5 resulting value will be greater than 4 so int will take 4 only that is what we need. So like this any number can be round off to nearest integer
@mohitratanpal272 жыл бұрын
@@Jack-mc7qe thx,now i understood,although i did the other way, i did(double)n--/i,and just return the ans
@shinosukenohara.123 Жыл бұрын
can u explain why this ?
@mohammadumaidansari50874 жыл бұрын
Recursion and DP is a nightmare for me and you explained it really well and some sort of magic i can see in your way of teaching. 😍😍😍 So Thank You So Much Bhaiyya...!! 😊
@kunalverma97773 жыл бұрын
Watch Aditya Verma for Recursion & DP. He is insane ❤
@riteshkhadse45174 жыл бұрын
wow..! perfectly explained..! 🔥🔥🔥 the Optimal solution was just Insane..🔥🔥
@coolyashvanjani2 жыл бұрын
I was able to come up with the Better Approach, but watching the Optimal one here blew my mind.
@alokgarg74943 жыл бұрын
In the first solution (with exponential time complexity) , the space complexity will not be exponential (as u said) it will be just O(m+n) for the recursion stack .
@bisatisrilatha79573 жыл бұрын
why m+n it is?????????
@gauravraj26043 жыл бұрын
Just loved your recurrence-tree explanation. That just solved a major part of the problem. Thanks Striver.
@stith_pragyaАй бұрын
UNDERSTOOD, Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@avneetsng3 жыл бұрын
HERE'S AN EXPLANATION TO THE ALGORITHM ~Algorithm : Combinatorial solution 1)Now we have observed that we can either go right(forward) or down 1.1) So as we can't go backwards or Up (ie every step we do make us go near the target) 1.2) => That we always take fixed amount of steps to reach the target 1.3) * total_steps = rows + cols - 2 2) Now this is just the problem of combination where we have to decide 2.1.a) In steps me se down steps kitne lene hai. (No. of ways to select down steps from total steps) => Total down_steps we take = (rows-1). => and No. of ways to select down steps from total steps => (total_steps C down_steps) OR 2.1.b) In steps me se right steps kitne lene hai. (No. of ways to select down steps from total steps ) => Total right_steps we take = (cols-1). => and No. of ways to select right steps from total steps => (total_steps C right_steps) => SO WE TAKE MIN OF DOWN_STEPS AND RIGHT_STEPS AND CALCULATE COMBINATON WITH THAT 3) Formula to calulate * (n C r) = n*(n-1)*(n-2)*(n-3)../1*2*3*..r. Now point to notice is that => No. of terms in denominator is 'r' => And No. of terms in numinator is also same as in denomintor ==> val=val*(steps-i+1)/i; i goes from 1 to min_of_right_steps_and_down_steps ; remember i should not be 0 , coz we are dividing with i , varna exception a jaega
@shivalikagupta34332 жыл бұрын
Amazing!!!! I have just being seen random videos from this series, till now because of interview purpose. But now I have decided to see this whole series, as soon as I am done with my work.
@deepakbhallavi4505 Жыл бұрын
Problem Introduction - 00:12 Sample Input - 00:33 Brute Force (Recursion) - 01:33 Recursion Code - 07:10 Optimization (Memorization) - 08:40 Memorization Code - 11:45 More Optimization - Combinatorics Method Observation 1 - 13:41 Observation 2 - 14:38 Solution Using Above Thought Process - 15:38 Java Code - 18:05 C++ Code - 18:54
@cryonim2 жыл бұрын
To understand approach 3 better, you can take a look at mister woo's paths across a grid video. Very good explaination as well.
@cryonim2 жыл бұрын
Here's the link: kzbin.info/www/bejne/o2jGmYOZbN98fJY
@ankurdahiya3611 Жыл бұрын
thx bro
@suchitragiri45463 жыл бұрын
It's clearly showing that how much you spent time on coding and your level of understanding outstanding... hat's up man!!
@parikshitrathore15104 жыл бұрын
wow man you made this probe. too easy and one more thing I can add is that you discuss both java and c++ program equally so , If someone skips an prog. than he/she can understand the second one too
@mostafa_rmstu61573 жыл бұрын
Awesome, You are saving our times and also giving the actual ways to learn. Thanks a lot
@aakashgarg83522 жыл бұрын
Surprised to see that no one noticed that at 12:20 in the Recursive and Memoized Code there was a huge mistake. In the code that instead of else return dp[i][j] = uniquePathsRecc(i+1,j,n,m,dp)+uniquePathsRecc(i,j+1,n,m,dp); , else return dp[i][j] = uniquePathsRecc(i+1,j,dp)+uniquePathsRecc(i,j+1,dp); was written. I am just pointing out .
@alokkumar-ki7wp2 жыл бұрын
I solved it using DP, I felt like this is it what better solution can exist now and then comes Combinatorics. Amazing solution Striver!
@sahilanower91893 жыл бұрын
That Combination solution was like finding a diamond out of coal.😊 How in Earth do you find such solutions!
@priyotoshsahaThePowerOf23 Жыл бұрын
bhai thoda zyada ho gya😄
@kaustavpaul93062 жыл бұрын
Best Explanation. People who don't know anything about recursion will also get a good idea about it.
@sourav.singh292 жыл бұрын
Just a Little Change, and Time Complexity will be min(m-1, n-1) int uniquePaths(int m, int n) { int N = n + m - 2; // total steps = n-1 + m-1 int r = min(n, m) - 1; // will iterate on the minimum of (n-1 or m-1) for efficiency double res = 1; // compute nCr eg - 10C3 for (int i = 1; i
@jaskiratsinghosahan46383 жыл бұрын
Very well explained 👍 . First time i understood the concept behind DP. Thank u bhai 🙂
@madhubabu39384 жыл бұрын
This is the first time I have seen the optimal solution for this problem.You are doing great job bhaiya.
@riyanshpal40634 жыл бұрын
bhaiya, i had done this question in past with a tc(n*m) and sc(m), but your optimal solution blows up my mind.
@mayankchaudhary55154 жыл бұрын
Everything was amazing, moving from brute recursive to combinatorics solution, but what I think is in the final code, where you took r = m - 1, you should take, r = min(n-1, m-1) suppose take the example, where n = 7 and m = 10, in this case, if we use r = m - 1, we have to iterate 9 times but if we use r = min(n-1, m-1), which according to me is more general, then we will have only 6 iterations. Btw awesome content....keep going :)
@takeUforward4 жыл бұрын
Yes, I said that, did not wanted to make the code complicated so kept is simple, but yes we can do that !
@sushmareddy13703 жыл бұрын
@@takeUforward Nice explanation Striver :) While calculating nCr, we can also do res = res* (N- -/i ) Eg. 6C3 = 6/1 * 5/2 * 4/3
@yatinarora12523 жыл бұрын
@@sushmareddy1370 simply do for(int i=1;i
@ranasauravsingh2 жыл бұрын
UNDERSTOOD.. .!!! Thanks striver for the video... :)
@yashpatni22034 жыл бұрын
Yes, understood all the 3 solutions, Thank you so much for this placement series and your efforts. 😊
@abhisheksunda30992 жыл бұрын
great solution! i think if we start i from 1 ( as shown in video) then it will perfectly divide the result (res), i.e. no need of declaring res as double it will work for int type also. i am not able to prove it mathematically, just a feeling that as we are increasing numerator and denominator with 1 then numerator will always be divisible(perfectly) by denominator i tried it on some examples and it holds. if someone can prove this right or wrong mathematically, it would be a great help!
@saranghae37202 жыл бұрын
This Question must be solved with DP approach, as interviewer needs an engineer who has problem solving skill instead of being mathematician... PS: Maths Approaches work on some specific questions....
@utkarshsharma66502 жыл бұрын
mathematics is the future, just see how much space and time can be optimized by inducing simple mathematics into solutions
@10daysAgo2 жыл бұрын
Wtf 🤦 engineering is basically using all the concepts of basic sciences ( plus mathematics) to solve a day to day life problem , it can be software related , health related or anything 😅. Obviously they will accept the maths solution wholeheartedly dude
@nahidfaraji5069 Жыл бұрын
int N = m + n - 2; int r = m-1; int res = 1; for(int i=1; i
@YogeshKumar-px5bd3 жыл бұрын
Great explanation. I know it takes guts to manage professional life and youtube both.
@uma_9184 жыл бұрын
Before jumping from recursion to Dp we first need to see if we have overlapping intervals like in this problem. Otherwise, DP doesn't work.
@takeUforward4 жыл бұрын
Yes that is what I said, I clearly pointed out that there were repeating states.
@uma_9184 жыл бұрын
@@takeUforward Yes you have mentioned it. I'm just letting the people know the thought process for DP problems.
@badass_yt7962 Жыл бұрын
Hands down Striver you are the best of all 🙌
@deweshjha81203 жыл бұрын
How to calculate the exact time complexity of Brute force approach?
@amanbhadani88402 жыл бұрын
The combination approrach is something new for me.Thanks a lot
@charliesdelta72623 жыл бұрын
No Kidding, This is the best solution/explanation for this problem 🙂🙂
@ericcartman47993 жыл бұрын
Thank you, you are a great teacher. Thanks for making these video and helping us.
@user-le3pr5mr1j8 ай бұрын
Amazing Wonderful explaination..
@devanshmesson27773 жыл бұрын
Such a clear explanation, much love striver!
@devangsingh29503 жыл бұрын
How can be the space complexity be exponential for the brute force, at a time the stack will hold path from 0,0 to m-1,n-1 which will be O(m+n) as we can only go right and left, but if we can move in any direction then we can say that the space complexity will be exponenetial. Is this correct?
@daminivyas71102 жыл бұрын
I think so if we can move in any direction, the max depth would be m*n so the space complexity would be O(m*n)
@bhaveshkumar68422 жыл бұрын
The worst case for the brute force will be a complete binary tree (where every node has two children). So, level 0 will have 1 node that is 2^0 nodes, level 1 will have 2 nodes that is 2^1 nodes, level 2 will have 4 nodes that is 2^2 nodes and level n will have 2^n nodes. So total number of nodes will be 2^0+2^1+2^2+...+2^N = (2^N+1) -1 (Using the formula for sum of geometric progression). (2^N+1) -1 is O(2^N). Nodes represent recursive calls. So 2^N nodes mean 2^N recursive calls and recursive calls use stack and each call uses space so space complexity will also be O(2^N)
@kalpkumudkumar81633 жыл бұрын
dude you deserve all the praise in the world ....
@bhaskarmaheshwari96274 жыл бұрын
u got my respect man
@mansilende87504 жыл бұрын
Awesome video bro. You perfectly explained the approaches and made it easy to understand :)
@pratikraut43874 жыл бұрын
Space complexity of recursive solution is not exponential it is O(2*n)
@takeUforward4 жыл бұрын
Yes you are correct, it is o(n + m), I messed that up!
@bisatisrilatha79573 жыл бұрын
O(m+n) how is it?
@surendarraj7153 жыл бұрын
@@bisatisrilatha7957 because the recursive call will eventually pile in stack for upto m and n
@prafulkatare10163 жыл бұрын
The optimal solution was just mind blowing, you are seriously awesome.
@rahulgarai48222 жыл бұрын
The most optimal approach is using permutation with repetation.
@PIYUSH-lz1zq Жыл бұрын
bro , y we not doing n*m-2 ??
@sakshigupta17773 жыл бұрын
The way you teach is Awesome!!Learned so much
@tanmaytyagi70313 жыл бұрын
the combinatorics approach is causing OVERFLOW
@kumkumslab58112 жыл бұрын
now i finally got one of the best teacher on youtube
@PIYUSH-lz1zq Жыл бұрын
bro , y we not doing n*m-2 ??
@rishabhkumar11703 жыл бұрын
This what I called an explanation you really are the best . Aise lag rha h ki ye SDE sheet krke job pakki h. Thanks bro 🙏🙏🙏
@pritishpattnaik46742 жыл бұрын
We can optimize with dp by memoization by using a 2d vector
@ashishrana-jw8ye Жыл бұрын
combinatorics approach was amazing
@sumedhvichare13883 жыл бұрын
Optimal solution just blew my mind! Great work bhaiya!
@md.imrankhan691211 ай бұрын
Thank you Mr. Legend
@srishtikdutta89464 жыл бұрын
When I saw the problem, directly the combinatorics approach came to my mind. What would be the impression on the interviewer if I directly gave that solution?
@sheikhaman62184 жыл бұрын
Ya same question... Is it okay if we directly go with optimal solution...
@suthakark18164 жыл бұрын
It's ok ,up until the point you are able to explain the intuition behind your solution.
@exodus59484 жыл бұрын
Bro, you have to fool the interviewer that ypu have not saw this problem before. Start from recursive.. then recursive + memo and finally dp. And at last you can also give the most optimised solution
@srishtikdutta89464 жыл бұрын
@@exodus5948 what if I have really not seen it before, the combinatorics is my natural move due to my JEE background.
@exodus59484 жыл бұрын
@@srishtikdutta8946 It doesnot matter to interviewer, if he sensed that you directly answered the most optimal approach but you are able to explain the intuition behind it. It is acceptable or in other case interviewer may bombard you with follow up questions.
@jitinkrishnamadineni32054 жыл бұрын
Thank you bro. You are my inspiration. I always like your videos.
@aakashyadav62284 жыл бұрын
Please never stop making videos. You are awesome.
@kushjoshi971610 ай бұрын
nice solution!
@Ajay7805 Жыл бұрын
Could you please help me understand the following? int uniquePaths(int m, int n) { int num = m+n-2; int den=1; double ans = 1; while(den
@ArpitKumar-yo6up2 жыл бұрын
Loved the video especially the part brute force to optimal
@manthanbhikadiya5924 жыл бұрын
Explanation Level🔥🔥🔥🔥 One of the best placement series 👍👍
@atharvjoshi89133 ай бұрын
amazing.
@shilpaparmar3611 Жыл бұрын
Amazing explanation.
@GauravThinks2 жыл бұрын
Newbies, go through recursion playlist before
@sunilpasari43704 жыл бұрын
One of your best videos bhaiya ❤️❤️
@sriramkk90044 жыл бұрын
One of the best explanations.Thank you
@ayushthakur7333 жыл бұрын
Awesome optimal method and great explanation ...but the dp approach is giving wrong ans on gfg
@subee12811 ай бұрын
Thanks
@bhaveshkumar68422 жыл бұрын
Thank you so much bro!!!!!!!!!
@JamesHalpert85552 жыл бұрын
If u can make a video on how to determine time and space complexity !!❤️
@AmitSingh-ut4wt2 жыл бұрын
Yes. The explanation was awesome
@kanhaiyatulsyan75603 жыл бұрын
and thats how you get rid of your dp fear....!!!!!
@2501Lucky4 жыл бұрын
Is it important to give combination form solution, as it might not strike for many. And how to develop an intuition for these mathematics solutions?
@takeUforward4 жыл бұрын
practice :)
@varnikagupta87883 жыл бұрын
In the last approach, why did we use double and not long long to store the result in 'res'?
@takeUforward3 жыл бұрын
Since division might give float, so to avoid precision err
@varnikagupta87883 жыл бұрын
@@takeUforward okay ty :)
@anmolagarwal56002 жыл бұрын
will the complexity of recursive brute force solution be: O( 2 ^ ( log(m*n) ) ) ? Or will it be: O( 2 ^ ( m*n ) )?
@bstcoder20883 жыл бұрын
bro at 7:20 see the else part where you are calling function , by the way thank you for making such kind of content this help me a lot and your cp list is outstanding iam growing in cp tnq you bro keep growing bro we are with you
@yatinarora12523 жыл бұрын
It's OK with else part 🙄
@NARUTOUZUMAKI-bk4nx7 ай бұрын
Understood
@abhinanda704911 ай бұрын
understood
@anshumanrout65054 жыл бұрын
I just wanted to ask I'm from mechanical and from tier 3 will I be able to sit for these big companies . Please answer my query
@suthakark18164 жыл бұрын
You have to get help through your acquaintances for referrals. Also try to approach people in linkdn
@neelpatel1223 жыл бұрын
Amazing solution.
@devanshmesson27773 жыл бұрын
Time complexity for bruteforce solution will be O(2^(m*n)) ?
@sohanagupta64603 жыл бұрын
your recursion explaination amazing.
@anishkumargiri9490 Жыл бұрын
japanah tusi great ho...................😎😎😎😎
@krish.strings Жыл бұрын
thala...how did u came up with the 3rd solution...I can't even imagine how human can end up with this idea.
@suyashmishra6946 Жыл бұрын
us. I am seriously considering watching your previous videos
@zeeshanhasankhan2 жыл бұрын
While watching striver video you must be consistent though >>>>
@wanderer_ankur4 жыл бұрын
wow man ! such a beautiful explanation ... :)
@ArjunSingh-pm2vt3 жыл бұрын
the optimal solution blew my mind
@sathyapriyaa48092 жыл бұрын
Ohh man! ur videos are great!! life saviour
@tempcoast_223 Жыл бұрын
Striver i have one Question What if the robot was allowed to move diagonally i camp up with the DP approach for that i don't know about this last optimized approach that how will we combine the solution for diagonal case. thanks for helping.
@pritishpattnaik46742 жыл бұрын
Fantastic explanation
@rishabhgoyal81104 жыл бұрын
Damn!!! BLESS YOU MAN!
@rashidaziz22152 жыл бұрын
class Solution { public: int uniquePaths(int m, int n) { if(m==1 || n==1){ return 1; } return uniquePaths(m-1,n)+uniquePaths(m,n-1); } }; you can use this too in recurssion method
@079k_pranayagrawal7 Жыл бұрын
What an explanation!!
@LegitGamer23453 жыл бұрын
In the recursive solution if i and j are set to 0 at start then how will I and j ever be greater than n and m respectively ?
@LegitGamer23453 жыл бұрын
Bhaiya can you explain this please I have just started coding and am stuck on this problem
@yatinarora12523 жыл бұрын
Just made recursion tree and write it in a base case