Unique Paths - Dynamic Programming - Leetcode 62

[@NeetCode]

Dynamic Programming Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@sviatoslavnovosiadlyi611]

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

[@wishall007]

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

[@sarvagyadwivedi2467]

if you in Quant, you are dealing with such challenging algorithmic questions on almost daily basis

[@tuminspace]

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"

[@PippyPappyPatterson]

Gonna start opening in interviews with this.

[@haosmark]

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.

[@vipinamar8323]

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.

[@aaron-ang]

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

[@nikitakalinovsky1686]

@@vipinamar8323 you can tho

[@PedanticAnswerSeeker]

@@vipinamar8323 row = [1] * n for i in range(1, m): for j in range(1, n): row[j] += row[j-1] return row[-1]

[@HR-pz7ts]

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!

[@director8656]

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

[@SajidAli-fn9tp]

Yes, it IS just a ton of practice.

[@sheesh7386]

DP is really about doing a lot of them. It's like "if you know, you know" type of problem

[@heyquantboy]

There's no way to go into an interview cold, get these types of questions and solve them in 15 minutes. Impossible.

[@quirkyquester]

Great explanation! Thx teacher! _ prevRow = [1] * n currRow = [None] * n for r in range(1, m): for c in range(n): currRow[c] = prevRow[c] if c > 0: currRow[c] += currRow[c - 1] prevRow, currRow = currRow, prevRow return prevRow[-1]

[@nyferox5637]

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.

[@srijanpaul]

Ah, good point! Thanks a lot ^^

[@Gameplay-ps9ub]

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.

[@bdac8525]

it is not constant time, although it is one line of code in python. It calculates factorial.

[@DemonixTB]

@@bdac8525 look up table is constant time, there is an upper bound so there is no need for the calculation of anything

[@ok-google-run]

can you please explain why so ?

[@tsuu2092]

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)

[@dumdumbringgumgum2940]

could you please elaborate??

[@michaelabateman1711]

what is C?

[@tsuu2092]

@@michaelabateman1711 It is combination. 8C6 means the number of ways to choose any 6 items from 8 items.

[@gitarowydominik]

Correct! This is not a DP problem. This can be solved in O(1) space by calculating the number of combinations.

[@dhij]

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)

[@infernape716]

i think technically this isn't DP, since its recursive it would be memoization

[@dhij]

@@infernape716 yup you are right :)

[@dhij]

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)

[@a2xd94]

I believe DFS would exceed the time limit for this problem. I attempted it that way and failed.

[@hitthemill8595]

@@a2xd94 nope it works

[@andrepinto7895]

* 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];

[@Being_phani]

Hey, can you please explain the idea behind your logic, it looks better and neater. It would be a great help!

[@Jbuckkz]

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.

[@pekarna]

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 }

[@ShubhamRajput-sq5ty]

i too thought the same.

[@workasm83]

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)

[@mateus.vasconcelos]

Indeed your logic is correct, but for the LeetCode problem it will probably face overflow for the edge cases, since it can compute 200!

[@---el6pq]

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

[@rrtt6903]

Simple Formula is: (m+n-2)/(m-1)!(n-1)! Does not matter weather m is greater or smaller or equal to n

[@tamilupk]

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?

[@geekydanish5990]

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]

[@NN-uy6ik]

nice one

[@NinjiaJoeLife]

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)"?

[@orellavie6233]

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)

[@TKNinja007]

@@orellavie6233 yea it ended up not mattering, I think its easier if you just have both loops iterating normally instead of backwards

[@manuelese8760]

Man this is tough for me. This problem is above me. Greetings from Argentina. I really like your content

[@rams2478]

Thanks man.. I like your voice and the way you go through the problem.. clear explanation...

[@hwang1607]

Heres a simpler solution using the logic in the unique paths 2 video: 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]

[@yingjielian4912]

Your explanation is the best among all of the explanations on the internet!

[@tuminspace]

I agree to this a 100%

[@liwensi1218]

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]

[@quirkyquester]

beautiful solution. thx brother!

[@scottishfoldmocha5875]

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]

[@muaathasali4509]

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

[@ok-google-run]

please explain why so

[@froobly]

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.

[@RandomShowerThoughts]

this was a fantastic video and perfectly describes how to tackle this type of problem

[@vgsuresh]

this is one of the amazing explanation for the problem.

[@Eleven-qb6rq]

Damn Dude, I never thought that solution will be this much easy for such hard problem. I love the way you explain approch❣

[@ns45766]

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

[@gurleensingh2600]

here's the imlementation in ruby with the help of recursion def unique_paths(rows,columns) if rows == 1 || columns == 1 return 1 end unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1) end

[@zhaovincent8039]

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]

[@MIHAINEM]

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

[@yacobplayz6524]

Here's a super simple solution with counting: return int(math.factorial(m+n-2)/(math.factorial(m-1)*math.factorial(n-1)))

[@RaspingOdin45]

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)

[@bzrkr444]

This exact question came up in my amazon interview for a grad sde role, wish I saw this video before

[@hkanything]

Since you can only go down and right, you can compute the permutation of (2+6)!/2!6!

[@americanonobrasil2128]

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.

[@shivambhardwaj7606]

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.

[@henryCcc8614]

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.

[@rrtt6903]

Simple Formula is: (m+n-2)/(m-1)!(n-1)! Does not matter weather m is greater or smaller or equal to n

[@edwardteach2]

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

[@arairyohei7457]

Thank you so much for your clarification adding line-by-line comments! Helped me understand it more clearly!!

[@notmidhun2365]

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

[@gitarowydominik]

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.

[@alekseiperedurowain7730]

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.

[@riddhimahajan6662]

Amazing explanation!!! Could you provide the explanation for Unique Paths II - Dynamic Programming - Leetcode 63 please :)

[@sidazhong2019]

using bottomRow and topRow instead of row and newRow

[@dewangpatil4990]

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

[@Push1781]

Striver has own YT vidoes on those as well. Also if you search by name you will get all videos on neetcode

[@ok-google-run]

@@Push1781 maybe for python solutions

[@freyappari]

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

[@vasundharachintada5264]

wow awesome explanation. thank you very much for detailed explanation

[@himanshuchourasia7383]

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]

[@mihailra9675]

The constant time formula is (m-1+n-1)! / (m-1)!*(n-1)!

[@a2xd94]

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

[@ninjaa9087]

the best explanation ever🔥🔥🔥

[@minabenjamin8232]

This is amazing, thank you!

[@jugsma6676]

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

[@sayChristIsKing]

wouldn't be easier to do it recursively uniquePath(m - 1 , n) + uniquePath(m , n - 1) ?

[@julianelmasry9556]

i believe the reason we dont do this is because of the repeated work. that is why we do it with the DP approach

[@joakimolovsson7310]

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.

[@AhmedEl-Kilany]

you're genius!

[@retrofacade9832]

dude what a solution!!!

[@reehji]

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?

[@AkVertasium232]

thaks a lot

[@iqrabismi68]

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]

[@raviy10]

Thank you !!!

[@kirbykidsmith]

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.

[@nikhil_a01]

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.

[@GwenPool99]

I think maths solution is (m+n-2) ! / (m-1)! * (n-1) !

[@m0nxt3r]

SUPER SICK!!!

[@YuzuWei]

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?

[@sachinnair1613]

if m == 1 or n == 1: return 1

[@PippyPappyPatterson]

`m=1; n=1` test case works fine for me.

[@aviralgupta9869]

Better solution could be made using Combination formula

[@Graverman]

I tried that, do you have any resources for the better solution?

[@iusmann]

AMAZING

[@dhruv7t861]

genius..!!!

[@mytj228]

Am I the only one having issues understanding the problem? Why 3, 7 = 28?

[@aaditya_87]

cpp run time 0ms😂😂