Thanks for yet another great video! Small note: If I am not mistaken your recursive solution doesn't work because you never collect the count when you are arriving to your base case, e.g something like this - if r == M - 1 and c == N - 1: return 1
We could also do it in O(1) space by using our obstacleGrid array as the dp array. We will use the same logic but we will store the total paths by it's negative value to differentiate between number of paths and the obstacle. In the end we will return absolute of the negative value at 0, 0.
here is a solution for unique paths 1 that I used this same logic to make: class Solution: def uniquePaths(self, m: int, n: int) -> int: row = [0] * n row[n-1] =1 for i in reversed(range(m)): for j in reversed(range(n-1)): row[j] = row[j] + row[j+1] return row[0]
To help those a little confused by the final code, neet makes a slight space-optimization of only using a single array, which confused me a bit and I don't think would be reasonable for an interview. The unique-Paths-1 solution uses the much more straight-forward optimization of only using two-arrays (one to represent the prev row and the other to represent the current row) and I think you're better off just using that approach for this one. Recognizing that you don't actually need that 2nd array to populate the current rows dp values is not realistic for an interview imo. Clever AF though
Great. You explain everything beginners might think and wonder. I can't complain anything about your videos. Thanks a lot neetcode
There’s an O(1) solution using combinatorics in which we break it into two matrix and exclude all paths which strikes rock
Could you elaborate on this? I'm not sure how this would be possible when there can be more than one obstacle
I like this problem. It is a very good and didactic example of dynamic programming.
Thanks for yet another great video! Small note: If I am not mistaken your recursive solution doesn't work because you never collect the count when you are arriving to your base case, e.g something like this - if r == M - 1 and c == N - 1:
return 1
The explanation for this solution is amazing!
We could also do it in O(1) space by using our obstacleGrid array as the dp array. We will use the same logic but we will store the total paths by it's negative value to differentiate between number of paths and the obstacle. In the end we will return absolute of the negative value at 0, 0.
Generally changing input is illegal
here is a solution for unique paths 1 that I used this same logic to make:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
row = [0] * n
row[n-1] =1
for i in reversed(range(m)):
for j in reversed(range(n-1)):
row[j] = row[j] + row[j+1]
return row[0]
these dp problems takes days to understand and after watching editorials 5-6 times. Any suggestions pls??
Great explanation as always!!
Elegant explanation
To help those a little confused by the final code, neet makes a slight space-optimization of only using a single array, which confused me a bit and I don't think would be reasonable for an interview. The unique-Paths-1 solution uses the much more straight-forward optimization of only using two-arrays (one to represent the prev row and the other to represent the current row) and I think you're better off just using that approach for this one. Recognizing that you don't actually need that 2nd array to populate the current rows dp values is not realistic for an interview imo. Clever AF though
Great,as usual.
This is a fake account, support the real neetcode
Actually this is my second channel - i post all the new LC videos here now :)