Це відео не доступне.
Перепрошуємо.
Grid Unique Paths | GOOGLE interview | BS-24. Search in a 2D Matrix - I | Binary Search of 2D
Вставка
- Опубліковано 31 сер 2020
- 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 ...
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
Yes, superb depth
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/
Yes
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
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 ==
The way you teach is nothing but magic.. And you are 100 % coder and 200% magician... 💥😎❤
I got to understand recursion first time in my entire life. Thanks man!!!
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
In 3rd approach we can take min (m, n) as r in Ncr method .I think this will helps to more optimze the code.
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);
}
Remove that if condition just return (int)(ans+0.5)
what does 0.5 here mean
@@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
@@Jack-mc7qe thx,now i understood,although i did the other way, i did(double)n--/i,and just return the ans
can u explain why this ?
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
wow..! perfectly explained..! 🔥🔥🔥
the Optimal solution was just Insane..🔥🔥
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...!! 😊
Watch Aditya Verma for Recursion & DP. He is insane ❤
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 .
why m+n it is?????????
I was able to come up with the Better Approach, but watching the Optimal one here blew my mind.
UNDERSTOOD, Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Just loved your recurrence-tree explanation. That just solved a major part of the problem. Thanks Striver.
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.
It's clearly showing that how much you spent time on coding and your level of understanding outstanding... hat's up man!!
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 .
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
I solved it using DP, I felt like this is it what better solution can exist now and then comes Combinatorics. Amazing solution Striver!
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
To understand approach 3 better, you can take a look at mister woo's paths across a grid video. Very good explaination as well.
Here's the link: ua-cam.com/video/m7chPc7zIF4/v-deo.html
thx bro
bhaiya, i had done this question in past with a tc(n*m) and sc(m), but your optimal solution blows up my mind.
Awesome, You are saving our times and also giving the actual ways to learn. Thanks a lot
UNDERSTOOD.. .!!!
Thanks striver for the video... :)
Very well explained 👍 . First time i understood the concept behind DP.
Thank u bhai 🙂
Best Explanation. People who don't know anything about recursion will also get a good idea about it.
That Combination solution was like finding a diamond out of coal.😊 How in Earth do you find such solutions!
bhai thoda zyada ho gya😄
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!
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 :)
Yes, I said that, did not wanted to make the code complicated so kept is simple, but yes we can do that !
@@takeUforward
Nice explanation Striver :)
While calculating nCr, we can also do res = res* (N- -/i )
Eg. 6C3 = 6/1 * 5/2 * 4/3
@@sushmareddy1370 simply do for(int i=1;i
Hands down Striver you are the best of all 🙌
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....
mathematics is the future, just see how much space and time can be optimized by inducing simple mathematics into solutions
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
int N = m + n - 2;
int r = m-1;
int res = 1;
for(int i=1; i
Great explanation. I know it takes guts to manage professional life and youtube both.
No Kidding, This is the best solution/explanation for this problem 🙂🙂
This is the first time I have seen the optimal solution for this problem.You are doing great job bhaiya.
How to calculate the exact time complexity of Brute force approach?
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?
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)
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)
Yes, understood all the 3 solutions, Thank you so much for this placement series and your efforts. 😊
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.
Yes that is what I said, I clearly pointed out that there were repeating states.
@@takeUforward Yes you have mentioned it. I'm just letting the people know the thought process for DP problems.
u got my respect man
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 🙏🙏🙏
Such a clear explanation, much love striver!
Amazing Wonderful explaination..
The combination approrach is something new for me.Thanks a lot
Please never stop making videos. You are awesome.
dude you deserve all the praise in the world ....
Thank you, you are a great teacher. Thanks for making these video and helping us.
Space complexity of recursive solution is not exponential it is O(2*n)
Yes you are correct, it is o(n + m), I messed that up!
O(m+n) how is it?
@@bisatisrilatha7957 because the recursive call will eventually pile in stack for upto m and n
The way you teach is Awesome!!Learned so much
now i finally got one of the best teacher on youtube
bro , y we not doing n*m-2 ??
One of your best videos bhaiya ❤️❤️
Awesome video bro.
You perfectly explained the approaches and made it easy to understand :)
The most optimal approach is using permutation with repetation.
bro , y we not doing n*m-2 ??
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
The optimal solution was just mind blowing, you are seriously awesome.
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
Thank you bro. You are my inspiration. I always like your videos.
Amazing explanation.
Explanation Level🔥🔥🔥🔥 One of the best placement series 👍👍
Newbies, go through recursion playlist before
the combinatorics approach is causing OVERFLOW
We can optimize with dp by memoization by using a 2d vector
Thank you Mr. Legend
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?
practice :)
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
You have to get help through your acquaintances for referrals. Also try to approach people in linkdn
Optimal solution just blew my mind! Great work bhaiya!
combinatorics approach was amazing
will the complexity of recursive brute force solution be: O( 2 ^ ( log(m*n) ) ) ?
Or will it be: O( 2 ^ ( m*n ) )?
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?
Ya same question... Is it okay if we directly go with optimal solution...
It's ok ,up until the point you are able to explain the intuition behind your solution.
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
@@exodus5948 what if I have really not seen it before, the combinatorics is my natural move due to my JEE background.
@@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.
Loved the video
especially the part brute force to optimal
Time complexity for bruteforce solution will be O(2^(m*n)) ?
nice solution!
One of the best explanations.Thank you
Yes. The explanation was awesome
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.
Amazing solution.
In the last approach, why did we use double and not long long to store the result in 'res'?
Since division might give float, so to avoid precision err
@@takeUforward okay ty :)
Thank you so much bro!!!!!!!!!
amazing.
your recursion explaination amazing.
Thanks for the amazing video. I have a question, will using double not result in losing precision at some point when finding nCr? Also, according to BODMAS rule, (N - r + i) / i will get calculated first to an integer resulting in loss of precision?
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 ?
Bhaiya can you explain this please I have just started coding and am stuck on this problem
Just made recursion tree and write it in a base case
japanah tusi great ho...................😎😎😎😎
us. I am seriously considering watching your previous videos
wow man ! such a beautiful explanation ... :)
Awesome optimal method and great explanation ...but the dp approach is giving wrong ans on gfg
Code for Striver's DP Approach:
class Solution {
public:
int solve(vector &dp, int &m, int &n, int i, int j)
{
if (i>=m || j>=n)
return 0;
else if (i==m-1 && j==n-1)
return 1;
else if (dp[i][j] != -1)
return dp[i][j];
else
return dp[i][j] = solve(dp, m, n, i+1, j) + solve(dp, m, n, i, j+1);
}
int uniquePaths(int m, int n) {
if (m==1 && n==1) // Special Case
return 1;
vector dp(m, vector(n, -1));
solve(dp, m, n, 0, 0);
return dp[0][0];
} // TC = O(m.n) SC = O(m.n)
};
Fantastic explanation
Really thankful to you for this tremendous video.
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
It's OK with else part 🙄
thanks brother, optimal solution is really fantastic brother
Ohh man! ur videos are great!! life saviour
very good explanation thanks!
Thanks
If u can make a video on how to determine time and space complexity !!❤️
Won't using double for calculating value and then converting it to int cause problem?
Why res *= (N-r+1)/i gave precision error and res = res*(N-r+1)/i is correct?
bhaiya can we do the question using the backtracking by checking whether it is a valid move or not?
What an explanation!!
Thanks for the explanation!
why is it not working by taking res as int
all the results of combinations are always int
While multiplying there might be an overflow.