Grid Unique Paths | GOOGLE interview | BS-24. Search in a 2D Matrix - I | Binary Search of 2D

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 ...

[@takeUforward]

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

[@2501Lucky]

Yes, superb depth

[@14Bishal]

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/

[@sahilchoudhary1473]

Yes

[@priyanshiagrawal9427]

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

[@LegitGamer2345]

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 ==

[@sheikhaman6218]

The way you teach is nothing but magic.. And you are 100 % coder and 200% magician... 💥😎❤

[@AjeetKumar-ty8zs]

I got to understand recursion first time in my entire life. Thanks man!!!

[@hrithikgarg0318]

In 3rd approach we can take min (m, n) as r in Ncr method .I think this will helps to more optimze the code.

[@Itskrmani]

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-mc7qe]

Remove that if condition just return (int)(ans+0.5)

[@mohitratanpal27]

what does 0.5 here mean

[@Jack-mc7qe]

@@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

[@mohitratanpal27]

@@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 ?

[@mohammadumaidansari5087]

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...!! 😊

[@kunalverma9777]

Watch Aditya Verma for Recursion & DP. He is insane ❤

[@riteshkhadse4517]

wow..! perfectly explained..! 🔥🔥🔥 the Optimal solution was just Insane..🔥🔥

[@coolyashvanjani]

I was able to come up with the Better Approach, but watching the Optimal one here blew my mind.

[@alokgarg7494]

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 .

[@bisatisrilatha7957]

why m+n it is?????????

[@gauravraj2604]

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..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@avneetsng]

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

[@shivalikagupta3433]

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

[@cryonim]

To understand approach 3 better, you can take a look at mister woo's paths across a grid video. Very good explaination as well.

[@cryonim]

Here's the link: kzbin.info/www/bejne/o2jGmYOZbN98fJY

[@ankurdahiya3611]

thx bro

[@suchitragiri4546]

It's clearly showing that how much you spent time on coding and your level of understanding outstanding... hat's up man!!

[@parikshitrathore1510]

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_rmstu6157]

Awesome, You are saving our times and also giving the actual ways to learn. Thanks a lot

[@aakashgarg8352]

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-ki7wp]

I solved it using DP, I felt like this is it what better solution can exist now and then comes Combinatorics. Amazing solution Striver!

[@sahilanower9189]

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😄

[@kaustavpaul9306]

Best Explanation. People who don't know anything about recursion will also get a good idea about it.

[@sourav.singh29]

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

[@jaskiratsinghosahan4638]

Very well explained 👍 . First time i understood the concept behind DP. Thank u bhai 🙂

[@madhubabu3938]

This is the first time I have seen the optimal solution for this problem.You are doing great job bhaiya.

[@riyanshpal4063]

bhaiya, i had done this question in past with a tc(n*m) and sc(m), but your optimal solution blows up my mind.

[@mayankchaudhary5515]

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 :)

[@takeUforward]

Yes, I said that, did not wanted to make the code complicated so kept is simple, but yes we can do that !

[@sushmareddy1370]

@@takeUforward Nice explanation Striver :) While calculating nCr, we can also do res = res* (N- -/i ) Eg. 6C3 = 6/1 * 5/2 * 4/3

[@yatinarora1252]

@@sushmareddy1370 simply do for(int i=1;i

[@ranasauravsingh]

UNDERSTOOD.. .!!! Thanks striver for the video... :)

[@yashpatni2203]

Yes, understood all the 3 solutions, Thank you so much for this placement series and your efforts. 😊

[@abhisheksunda3099]

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!

[@saranghae3720]

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....

[@utkarshsharma6650]

mathematics is the future, just see how much space and time can be optimized by inducing simple mathematics into solutions

[@10daysAgo]

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-px5bd]

Great explanation. I know it takes guts to manage professional life and youtube both.

[@uma_918]

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.

[@takeUforward]

Yes that is what I said, I clearly pointed out that there were repeating states.

[@uma_918]

@@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 🙌

[@deweshjha8120]

How to calculate the exact time complexity of Brute force approach?

[@amanbhadani8840]

The combination approrach is something new for me.Thanks a lot

[@charliesdelta7262]

No Kidding, This is the best solution/explanation for this problem 🙂🙂

[@ericcartman4799]

Thank you, you are a great teacher. Thanks for making these video and helping us.

[@user-le3pr5mr1j]

Amazing Wonderful explaination..

[@devanshmesson2777]

Such a clear explanation, much love striver!

[@devangsingh2950]

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?

[@daminivyas7110]

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)

[@bhaveshkumar6842]

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)

[@kalpkumudkumar8163]

dude you deserve all the praise in the world ....

[@bhaskarmaheshwari9627]

u got my respect man

[@mansilende8750]

Awesome video bro. You perfectly explained the approaches and made it easy to understand :)

[@pratikraut4387]

Space complexity of recursive solution is not exponential it is O(2*n)

[@takeUforward]

Yes you are correct, it is o(n + m), I messed that up!

[@bisatisrilatha7957]

O(m+n) how is it?

[@surendarraj715]

@@bisatisrilatha7957 because the recursive call will eventually pile in stack for upto m and n

[@prafulkatare1016]

The optimal solution was just mind blowing, you are seriously awesome.

[@rahulgarai4822]

The most optimal approach is using permutation with repetation.

[@PIYUSH-lz1zq]

bro , y we not doing n*m-2 ??

[@sakshigupta1777]

The way you teach is Awesome!!Learned so much

[@tanmaytyagi7031]

the combinatorics approach is causing OVERFLOW

[@kumkumslab5811]

now i finally got one of the best teacher on youtube

[@PIYUSH-lz1zq]

bro , y we not doing n*m-2 ??

[@rishabhkumar1170]

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 🙏🙏🙏

[@pritishpattnaik4674]

We can optimize with dp by memoization by using a 2d vector

[@ashishrana-jw8ye]

combinatorics approach was amazing

[@sumedhvichare1388]

Optimal solution just blew my mind! Great work bhaiya!

[@md.imrankhan6912]

Thank you Mr. Legend

[@srishtikdutta8946]

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?

[@sheikhaman6218]

Ya same question... Is it okay if we directly go with optimal solution...

[@suthakark1816]

It's ok ,up until the point you are able to explain the intuition behind your solution.

[@exodus5948]

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

[@srishtikdutta8946]

@@exodus5948 what if I have really not seen it before, the combinatorics is my natural move due to my JEE background.

[@exodus5948]

@@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.

[@jitinkrishnamadineni3205]

Thank you bro. You are my inspiration. I always like your videos.

[@aakashyadav6228]

Please never stop making videos. You are awesome.

[@kushjoshi9716]

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-yo6up]

Loved the video especially the part brute force to optimal

[@manthanbhikadiya592]

Explanation Level🔥🔥🔥🔥 One of the best placement series 👍👍

[@atharvjoshi8913]

amazing.

[@shilpaparmar3611]

Amazing explanation.

[@GauravThinks]

Newbies, go through recursion playlist before

[@sunilpasari4370]

One of your best videos bhaiya ❤️❤️

[@sriramkk9004]

One of the best explanations.Thank you

[@ayushthakur733]

Awesome optimal method and great explanation ...but the dp approach is giving wrong ans on gfg

[@subee128]

Thanks

[@bhaveshkumar6842]

Thank you so much bro!!!!!!!!!

[@JamesHalpert8555]

If u can make a video on how to determine time and space complexity !!❤️

[@AmitSingh-ut4wt]

Yes. The explanation was awesome

[@kanhaiyatulsyan7560]

and thats how you get rid of your dp fear....!!!!!

[@2501Lucky]

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?

[@takeUforward]

practice :)

[@varnikagupta8788]

In the last approach, why did we use double and not long long to store the result in 'res'?

[@takeUforward]

Since division might give float, so to avoid precision err

[@varnikagupta8788]

@@takeUforward okay ty :)

[@anmolagarwal5600]

will the complexity of recursive brute force solution be: O( 2 ^ ( log(m*n) ) ) ? Or will it be: O( 2 ^ ( m*n ) )?

[@bstcoder2088]

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

[@yatinarora1252]

It's OK with else part 🙄

[@NARUTOUZUMAKI-bk4nx]

Understood

[@abhinanda7049]

understood

[@anshumanrout6505]

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

[@suthakark1816]

You have to get help through your acquaintances for referrals. Also try to approach people in linkdn

[@neelpatel122]

Amazing solution.

[@devanshmesson2777]

Time complexity for bruteforce solution will be O(2^(m*n)) ?

[@sohanagupta6460]

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

[@zeeshanhasankhan]

While watching striver video you must be consistent though >>>>

[@wanderer_ankur]

wow man ! such a beautiful explanation ... :)

[@ArjunSingh-pm2vt]

the optimal solution blew my mind

[@sathyapriyaa4809]

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.

[@pritishpattnaik4674]

Fantastic explanation

[@rishabhgoyal8110]

Damn!!! BLESS YOU MAN!

[@rashidaziz2215]

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!!

[@LegitGamer2345]

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 ?

[@LegitGamer2345]

Bhaiya can you explain this please I have just started coding and am stuck on this problem

[@yatinarora1252]

Just made recursion tree and write it in a base case

[@rajatsingh4233]

Really thankful to you for this tremendous video.

[@himanidave2051]

Thanks for the explanation!

[@devkinandansharma9554]

Bhai ka knowledge level is on another level 🔥🔥