Unique Paths - Dynamic Programming - Leetcode 62
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
Code on Github: github.com/neetcode-gh/leetco...
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/count-paths
0:00 - Read the problem
0:55- Drawing solution
8:20 - Coding Solution
leetcode 62
This question was identified as a Google interview question from here: github.com/xizhengszhang/Leet...
#dynamic #programming #python - Věda a technologie
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
Dynamic Programming Playlist: czcams.com/video/73r3KWiEvyk/video.html
Been working as SWE for 8 years. Never had to deal with problems like that but I do understand its necessary for interview. Was having really hard time understanding concept on coming with solution on my own but your videos are pure gold..
This problem actually has an important use case in Hidden Markov Models and modern speech recognition systems in the form of the forward-backward algorithm (en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm).
if you in Quant, you are dealing with such challenging algorithmic questions on almost daily basis
The intro itself is so addictive that when I try to solve a problem
I'd say it out
"Hello everyone let's solve somemore neetcode today"
Gonna start opening in interviews with this.
Your way of teaching is so good that I didn't even had to wait for you to code and I coded it myself just by using your logic. Thanks man!
Great explanation. Code can be simplified. There's no reason to hold 'newRow', you can just do it all with 'row', and there's no reason to track backwards, you can move forward (which feels more intuitive) with return row[-1] at the end.
I dont think you can solve it using a single row, you need access to the previous row to compute the next row. Feel free to post the solution here.
@@vipinamar8323 Here's my solution:
def uniquePaths(self, m: int, n: int) -> int:
row = [0] * (n-1) + [1]
for i in range(m):
for j in range(n-2, -1, -1):
row[j] += row[j+1]
return row[0]
@@vipinamar8323 you can tho
@@vipinamar8323
row = [1] * n
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[-1]
Great explanation. The answer for the constant time solution is just (m + n - 2) choose (m - 1), which is equal to (m + n - 2)! / ((m - 1)! * (n - 1)!). This is because you know that you have to have (m - 1) moves down and (n - 1) moves right, so you just need to choose where those (m - 1) downs or (n - 1) rights go and then you are done.
Ah, good point! Thanks a lot ^^
That's the solution I came up with initially and it's good for this problem. But on leetcode there is a similar question, but some fields are filled with obstacles and then I couldn't make combinatorics / mathematics solution work.
it is not constant time, although it is one line of code in python. It calculates factorial.
@@bdac8525 look up table is constant time, there is an upper bound so there is no need for the calculation of anything
can you please explain why so ?
I understand these solutions, but I could never think of these. How exactly do I go about learning the method to derive, is it just a ton of practice?, great video by the way
Yes, it IS just a ton of practice.
DP is really about doing a lot of them. It's like "if you know, you know" type of problem
There's no way to go into an interview cold, get these types of questions and solve them in 15 minutes. Impossible.
Here is my solution using math:
Let's say the width is 7 and the height is 3, which means your path will consists of 6R and 2D in any order. So in 8 possible moves, we fill 6 moves with R, which is 8C6 (or 8C2 if you consider D instead) ways total.
The generalized formula would be (w+h-2)C(w-1)
could you please elaborate??
what is C?
@@michaelabateman1711 It is combination. 8C6 means the number of ways to choose any 6 items from 8 items.
Correct! This is not a DP problem. This can be solved in O(1) space by calculating the number of combinations.
this is one of the amazing explanation for the problem.
this was a fantastic video and perfectly describes how to tackle this type of problem
Thanks man.. I like your voice and the way you go through the problem.. clear explanation...
Alternative approach:
We need to take 6 steps right and 2 down, in various order.
That means, a permutation of 2 sets of A == 6 and B == 2.
That means: (A + B) ! / (A! x B!)
E.g. 8! / (2! x 6!) = 28.
This is only possible because of the homogenity of the underlying graph (grid).
The problem of high numbers can be addressed by cancelling out the common parts of the factorials.
Then it can be sped up by memoization.
Even without that, this is faster than 82 %:
class Solution {
fun uniquePaths(m: Int, n: Int): Int {
val a = m -1
val b = n-1
return ( fact(a + b) / fact(a) / fact(b) ).toInt()
}
}
fun fact(num: Int): BigInteger {
var factorial = 1.toBigInteger()
for (i in num downTo 2) {
factorial = factorial.multiply(i.toBigInteger())
}
return factorial
}
i too thought the same.
This is the same as computing a binomial coeff C(A + B, B).So, one can use a recursive formula: C(n,k) = C(n-1,k-1) + C(n-1,k)
Indeed your logic is correct, but for the LeetCode problem it will probably face overflow for the edge cases, since it can compute 200!
Great video bro. Just put some of my own code may be easier to read in case any one interesting.
Most optimal DP solution 1D array:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for r in range(m-2, -1, -1):
for c in range(n-2, -1, -1):
dp[c] += dp[c+1]
return dp[0]
Less efficient DP with 2D array:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(2)]
for r in range(m-2, -1, -1):
for c in range(n-2, -1, -1):
dp[r%2][c] = dp[(r+1)%2][c] + dp[r%2][c+1]
return dp[0][0]
Basic DP solution with no optimization in space complexity:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n ] * m
for r in range(m-2, -1, -1):
for c in range(n-2, -1, -1):
dp[r][c] = dp[r+1][c] + dp[r][c+1]
return dp[0][0]
Amazing. Been loving the explanations. Any chance to do Unique paths II? Having trouble incorporating the obstacle and want to implement a similar solution to this one. Thanks, NeetCode.
Man this is tough for me. This problem is above me. Greetings from Argentina. I really like your content
Came here to say the way I solved this was by realizing that the filled out spaces matched the values of Pascal's Triangle, just rotated. So if you move m spaces down the right side of the triangle and n spaces down the left side, the intersection of those two diagonals is going to be the solution.
For example for m = 7 and n = 3, go 7 spaces down the right side of the triangle to reach the level (1, 6, 15, 20, 15, 6, 1) and 3 spaces down the left to reach level (1, 2, 1), the intersection is at level 9 (1, 8, 28, 56, 70, 56, 28, 8, 1), and 3 spaces in. There is already an equation for finding a value of Pascal's Triangle at level A and position B, which is A! / B!(A - B)!
Note that m and n DO NOT EQUAL A and B, because they represent a grid that corresponds to the values of the triangle rotated 90 degrees. To get the A and B values you have to compute:
B = min(m, n) - 1 //We subtract 1 because the math formula defines the top of the triangle as the 0th level. This is the position on the level that we need to get to.
A = m + n - 2//We subtract 1 each for m and n, and then add them together to get the level that our solution will be on.
My final solution in Java:
import java.math.BigInteger;
class Solution {
public int uniquePaths(int m, int n) {
int b = Math.min(m, n) - 1;
int a = m + n - 2;
return fact(a).divide(fact(b).multiply(fact(a - b))).intValue();
}
public BigInteger fact(int val) {
BigInteger factorial = BigInteger.ONE;
for (int i = 1; i
Simple Formula is: (m+n-2)/(m-1)!(n-1)!
Does not matter weather m is greater or smaller or equal to n
Damn Dude,
I never thought that solution will be this much easy for such hard problem.
I love the way you explain approch❣
I was surprised you didn't take your usual approach using dfs and dp set. This is another implementation with the same concept for anyone who might be interested.
def uniquePaths(self, m: int, n: int) -> int:
dp = {}
def dfs(r, c):
if r == m - 1 and c == n - 1:
return 1
if (r,c) in dp:
return dp[(r,c)]
if (r < 0 or r == m or
c < 0 or c == n):
return 0
dp[(r,c)] = dfs(r+1, c) + dfs(r, c+1)
return dp[(r,c)]
return dfs(0,0)
i think technically this isn't DP, since its recursive it would be memoization
@@infernape716 yup you are right :)
Here is an updated example to get rid of the duplicate returns of dp[(r,c)]:
def uniquePaths(self, m: int, n: int) -> int:
dp = {}
dp[(m-1,n-1)] = 1
def dfs(r, c):
if r == m or c == n:
return 0
if (r,c) not in dp:
dp[(r,c)] = dfs(r+1, c) + dfs(r, c+1)
return dp[(r,c)]
return dfs(0,0)
I believe DFS would exceed the time limit for this problem. I attempted it that way and failed.
@@a2xd94 nope it works
wow awesome explanation. thank you very much for detailed explanation
Your explanation is the best among all of the explanations on the internet!
I agree to this a 100%
This is amazing, thank you!
you could have rotated that grid picture and start counting from top left corner instead of counting backwards, also can reuse same row:
def uniquePaths(m, n):
row = [1] * n
for i in range(0, m-1):
for j in range(0, n):
if j==0:
row[j] = 1
else:
row[j] += row[j-1]
return row[n-1]
the best explanation ever🔥🔥🔥
Amazing explanation!!!
Could you provide the explanation for Unique Paths II - Dynamic Programming - Leetcode 63 please :)
Great solution thank you for it.
I've noticed that this could be simplfied further. we can calculate everything `in place` using only row.
As in your solution we fill the row with ones.
and iterate height times and just calculate row[i] += row[i + 1];
example code here:
int uniquePaths(int m, int n) {
std::vector v(n, 1); //size n fill 1
for(int c = 1; c < m; ++c)
{
for(int i = v.size() - 2; i >= 0; --i)
v[i] += v[i + 1];
}
return v[0];
}
Continue the good work, I appreciate your videos :)
why the first for loop is "for i in range(m - 1)"? I thought we go back from bottom right to upper left. Should it be "for i in range(m-1,-1,-1)"?
Asked the same question, but as you can see in the algo itself, no need for i, so it is the same. Sometimes it required to start from rithtmost and sometimes it doesn't (like coin change 1/2)
@@orellavie6233 yea it ended up not mattering, I think its easier if you just have both loops iterating normally instead of backwards
I immediately seized on the combinatorics solution for this, but it has some major gotchas. If you remember nCr ("n choose r"), the formula is n!/r!(n-r)!. But lower-level programming languages don't tend to have a built-in factorial function. And even if you do use a language with a built-in factorial, your CPU isn't going to have a factorial op code, so the library is still going to be executing an algorithm to compute it, which will run in linear time. So the mathematical formula will not give you a constant time solution, but it will give you a linear solution, which is still a pretty big improvement over O(n*m).
The next problem, though, is that if you naively compute that formula above by just multiplying the numbers together, you'll notice that the numerator gets enormous, and quickly overflows the integer space of any common programming language. Javascript won't error out, but it will switch to floating point mode, which will introduce rounding errors once you start dividing.
If you remember having to compute combinations in high school, you'll probably remember the trick I used here, which is instead of computing the whole factorials, notice that r! cancels the first r terms of n!, so instead, just compute the products of the numbers from r + 1 to n, and then divide by (n-r)!. Then you only have one big factorial to deal with, and if you choose your r to be larger than n - r, then you reduce the number of factorial terms by at least half, which is enough to skate by on Leetcode's test cases.
This got me in the 96th percentile for speed, and usually I'm smack dab in the middle of the pack.
Forward path solution,
def uniquePaths(self, m: int, n: int) -> int:
tempRow = [1] * n
for row in range(1, m):
for col in range(1, n):
# we are using the current col value before reassigning it
tempRow[col] = tempRow[col - 1] + tempRow[col]
return tempRow[-1]
Is it a good approach in terms of maintainability?
i feel this is more self explanatory
solution def uniquePaths(self, m: int, n: int) -> int:
dp = [[1 for j in range(n)] for i in range(m)]
for j in range(n-2,-1,-1):
for i in range(m-2,-1,-1):
dp[i][j] = dp[i][j+1] + dp[i+1][j];
return dp[0][0]
nice one
My O(1) solution for this would be:
distance = n - 1 + m - 1 # in this example would be 8, 2 downs and 6 rights
return (distance * (distance - 1)) // 2
NeetCode is where I come when my polished, commented code fails test case 97 by "Time limit exceeded".
...
Only to get 0:13 into the video and smack my forehead as the right approach becomes obvious in a flash.
The problem can also be solved mathematically as a combinations problem. We can move m-1 times down and n-1 times right, so we just find how many arrangements of each are possible by calculating n+m-2 choose m-1 = (n + m - 2)! / (m-1)!(n-1)!
The largest factorial calculation is n+m-2 which corresponds to a time complexity of O(n+m) instead of O(n*m).
please explain why so
* You don't need to start from the last position and move backwards. You can start from the first position and move to the target (which seems more natural).
* There is no need to create new arrays for each new row (that is inefficient). You can reuse the same array throughout all the rows.
Java:
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j-1];
return dp[n-1];
Hey, can you please explain the idea behind your logic, it looks better and neater. It would be a great help!
wow this is great. starting from the last position always throws me off with neetcode solutions. starting in the first position perfectly and intuitively describes bottom up approach to me.
dude what a solution!!!
A simple to understand, forwards approach:
ROWS * COLUMNS
dp = [ [1] * n ] * m
for r in range(1, m):
for c in range(1, n):
CURRENT POSITION VALUE = SUM OF TOP/LEFT POSITIONS
dp[r][c] = dp[r-1][c] + dp[r][c-1]
RETURN BOTTOM RIGHT VALUE
return dp[-1][-1]
TIME: O(n * m)
SPACE: O(n)
Since you can only go down and right, you can compute the permutation of (2+6)!/2!6!
My code based on the math :) O(n)
def uniquePaths(self, w: int, h: int) -> int:
n, k = h + w - 2, w - 1
fact = 1
for i in range(k):
fact *= n - i
fact //= i + 1
return fact
Simple Formula is: (m+n-2)/(m-1)!(n-1)!
Does not matter weather m is greater or smaller or equal to n
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
grid = [[0 for i in range(n)] for j in range(m)]
for i in range(n):
grid[m-1][i] = 1
for j in range(m):
grid[j][n-1] = 1
for i in range(m-2,-1,-1):
for j in range(n-2,-1,-1):
grid[i][j] = grid[i][j+1]+grid[i+1][j]
return grid[0][0]
I guess this simplifies the solution.
SUPER SICK!!!
using bottomRow and topRow instead of row and newRow
you're genius!
A think a tabular dynamic programming approach is more straightforward.
NumWays[row][col] = NumWays[row-1][col] + NumWays[row][col-1]
Then return value in the bottom right after the iteration.
Thank you !!!
This is not a DP problem. This can be solved in O(1) space by calculating the number of combinations: m+n-2 C n-1.
Hello Sir i am a big fan......I have a very important request....... Could you please make solution playlist of Striver's SDE Sheet. Its will be very beneficial for us students
Striver has own YT vidoes on those as well. Also if you search by name you will get all videos on neetcode
@@Push1781 maybe for python solutions
Spent 1/2 an hour creating an adjacency list and attempting to tackle this via DFS only to (facepalm) when seeing the 10-line 'clever' solution...
The constant time formula is (m-1+n-1)! / (m-1)!*(n-1)!
AMAZING
U a God.
Here's my Python solution:
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int - row
:type n: int - col
:rtype: int
"""
res = [[0] * (n + 1) for _ in range(m + 1)] # create the grid of (m+1)*(n+1)
res[m - 1][n - 1] = 1 # set our finish/base/end to 1, if you don't set it, your answer will be 0
for r in range(m - 1, -1, -1): # loop backwards
for c in range(n - 1, -1, -1): # loop backwards
res[r][c] += res[r + 1][c] + res[r][c + 1] # make sure to do += because if you don't your last answer will be 0
return res[0][0] # this should be the sum of all the unique paths at the start
Thank you so much for your clarification adding line-by-line comments!
Helped me understand it more clearly!!
i do have a doubt even though there is less code how do you come up with this solution in an interview without seeing this same problem
why starting from the finish? I start from the start, then the code will be,
dp =[1] * (m)
for row in range(1, n):
for col in range(1, m):
dp[col] += dp[col-1]
return dp[m-1]
I have top-down approach
def uniquePaths(self, m: int, n: int) -> int:
cache = [[0 for _ in range(n)] for _ in range(m)]
cache[0][0] = 1
for i in range(m):
for j in range(n):
if i > 0 and j > 0:
cache[i][j] = cache[i-1][j] + cache[i][j-1]
if (i 0):
cache[i][j] = 0 + cache[i][j-1]
if (i > 0) and (j
genius..!!!
def uniquePaths(self, m: int, n: int) -> int:
grid= [[0 for i in range(n+1)] for k in range(m+1)]
grid[m-1][n-1] = 1
for i in range(m-1,-1,-1):
for j in range(n-1,-1,-1):
if grid[i][j] ==0 :
grid[i][j] = grid[i+1][j] + grid[i][j+1]
return grid[0][0]
Simplified approach based on this video:-
Please like if you find useful.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
grid = [[0 for i in range(n+1)] for j in range(m+1)]
grid[m - 1][n]=1
for m in range(m-1, -1, -1):
for n in range(len(grid[m])-2, -1, -1):
grid[m][n] = grid[m][n+1] + grid[m+1][n]
return grid[0][0]
i dont have any work experience or design experience. I am from data engineering/data science. Can i leetcode my way to backend in FAANG :v?
Why does LeetCode and everyone use n as the number of rows?
It's a mxn matrix. Meaning m rows and n columns.
Nothing in the problem but something I've noticed throughout.
Even the official solution uses n as the rows.
wouldn't be easier to do it recursively uniquePath(m - 1 , n) + uniquePath(m , n - 1) ?
i believe the reason we dont do this is because of the repeated work. that is why we do it with the DP approach
kind of unfortunate that this isn't generic. of course the solution is efficient but it's not really helpful in thinking about memoization or using dynamic programming principles. would have been good if you could suggest your solution as an alternative intuition but provided a generic solution. Especially since a similar problem appears in CTCI but there are potential obstacles in the grid, which forces you to do an O(MN) solution.
This is a generic solution. A lot of DP problems look like this. If the grid contains obstacles you can still use a similar solution. A version with obstacles is available on LeetCode as LeetCode 63: Unique Paths II by the way.
It's different from the CTCI problem though because it asks for the number of possible paths, and not to find a single path. Finding a single path sounds more like a graph problem to me.
Better solution could be made using Combination formula
I tried that, do you have any resources for the better solution?
Your solution did not take into consideration when m = 1, which can only have one path. It would result in 'referenced before assignment error'. May I know if there is an elegant way to handle the special case?
if m == 1 or n == 1: return 1
`m=1; n=1` test case works fine for me.
Am I the only one having issues understanding the problem? Why 3, 7 = 28?
cpp run time 0ms😂😂