Builds on Linear DP, which you haven’t finished yet.
2D DP: Grid Paths (Unique Paths, Minimum Path Sum)
Picture a robot dropped onto the top-left cell of an m x n grid, aiming for the bottom-right cell. On every move it can step either one cell down or one cell right -- nothing else.
Given the grid dimensions m and n, count how many distinct routes the robot could take from start to finish. You can assume the true count never exceeds 2 * 109.
3 x 7 grid.Grid DP
grid dp[i][j] ➔ depends on the cell above and the cell to the left ➔ 1D rolling row| 1 | def unique_paths(m: int, n: int) -> int: |
| 2 | """Unique Paths: count right/down paths in an m x n grid with one rolling row. |
| 3 | Time: O(M * N) | Space: O(N) |
| 4 | """ |
| 5 | # row: one rolling row of the DP grid; row[j] starts at 1 since row 0 is reached only by moving right |
| 6 | row = [1] * n |
| 7 | for _ in range(1, m): |
| 8 | for j in range(1, n): |
| 9 | # 1. Combine Above And Left: |
| 10 | # row[j] still holds the count from the row above; add row[j - 1], already updated for this row. |
| 11 | row[j] += row[j - 1] |
| 12 | return row[n - 1] |
i is filled, row[j] is the answer for grid cell (i, j) for every j.Give every grid cell (i, j) one answer, and build it only from the cell above and the cell to its left. Fill the grid row by row, so both cells are already final, and keep just one rolling row: row[j] still holds the answer from above when you add row[j - 1], the answer from the left. The trap is the first column: row[0] has no left neighbour and stays 1, so the inner loop must start at j = 1; starting at 0 reads row[-1], the last cell.
See it run
Unique Paths, step by step (3 by 3 grid)
row -row[n - 1] -
Row i is the list row after grid row i is filled. Column j is the grid column j.
newthe cell being writtenabovethe cell one row up, which is readleftthe cell one column to the left, which is readanswerthe final answer
Start: unique_paths(3, 3) counts the right and down paths in a grid with 3 rows and 3 columns.
Gotcha 1 of 3
- The trap
Gotcha 1: Starting
jat 0 inunique_pathsMistakefor j in range(0, n):Fixfor j in range(1, n):What happens: Column 0 is reached in exactly one way, so
row[0]must stay 1. Withj = 0, the line readsrow[-1], which is the last cell. Python raises no error. On one column,row[0] += row[0]doubles the cell on every row.Example: m = 5, n = 1Mistake: returns 16Fix: returns 1
- Two strings are compared prefix by prefix, so a cell also looks at the cell diagonally up and to the left, as in Edit Distance (LC 72), and there is no grid to walk through. See Two-Sequence DP
- The state is one range of a single sequence, built from shorter ranges inside it, as in Longest Palindromic Subsequence (LC 516), not a path from a corner of a grid. See Interval DP
Deep Dive
What one cell means
A grid DP gives every cell (i, j) one answer, and the answer is final once the cell is written. In unique_paths, row[j] after row i is the number of paths from the top-left corner to cell (i, j), when the walker moves only right or down.
The state is a pair of positions, so the number of states is the number of cells: M * N for a grid with M rows and N columns.
The same table shape works when the answer is not a count. In Minimum Path Sum (LC 64), a cell holds the smallest total cost of a path to it.
Why the recurrence is correct
A path that ends at cell (i, j) made its last move either down, from the cell above, or right, from the cell to the left. These two groups share no path, and together they contain every path. So the count is above + left, which the code writes as row[j] += row[j - 1].
The first row and the first column have only one neighbour. Each of their cells is reached in exactly one way, by moving along the edge. This is why row starts as [1] * n, and why the inner loop starts at j = 1.
Example: for m = 3 and n = 3, row is [1, 1, 1] at the start. After the second row it is [1, 2, 3]. After the third row it is [1, 3, 6], so unique_paths(3, 3) returns 6.
For Minimum Path Sum (LC 64), the sum is replaced by a minimum plus the cell's cost: row[j] = min(row[j], row[j - 1]) + cost. For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7.
Fill order and why one row is enough
Cell (i, j) reads only the cell above and the cell to the left. Both are final before the cell is computed, if rows are filled from top to bottom and each row from left to right.
Only the previous row is ever read. So one array row is enough. When the loop reaches row[j], that cell still holds the value of the row above. The cell row[j - 1] was already updated for the current row. Their sum is the paths from above plus the paths from the left.
This is why the space is O(N), the width of one row, and not O(M * N) for the whole grid.
The cost, a formula, and what blocks it
Each cell is computed once with constant work. So the time is O(M * N). For a 1000 by 1000 grid, that is one million cell updates. The space is O(N).
For plain Unique Paths (LC 62) there is also a closed formula. Every path has m - 1 down moves and n - 1 right moves. The number of paths is the number of ways to choose where the down moves go, which is C(m + n - 2, m - 1). For m = 3 and n = 7 it is 28, the same as unique_paths(3, 7).
The formula stops working when a cell is blocked, as in Unique Paths II (LC 63), or when a cell has a cost, as in Minimum Path Sum (LC 64). The table handles both, so it is the general tool.
60-Second Pitch
"A brute force tries every path, which takes exponential time. I define one cell (i, j) as the answer for the walker that stops there. A path ends with a move down or a move right, so the cell depends only on the cell above and the cell to the left. The first row and column are reached one way each, so I start with a row of ones. Then I fill row by row, and I add row[j - 1] to row[j]. There are M times N cells with constant work each, so the time is O(M * N). I keep one row, so the space is O(N)."
Common Questions
- What are the time and space complexity of
unique_paths? O(M * N) time, because each cell does constant work.
O(N)space, because the code keeps one row of widthN.- Why is a single row enough?
Each cell reads only the cell above and the cell to the left. When the loop reaches
row[j], it still holds the value from the row above, androw[j - 1]was already updated for the current row. No older row is read.- How does the code change for obstacles, as in Unique Paths II (LC 63)?
A blocked cell has 0 paths, so the code sets
row[j] = 0for it. Start withrow = [0] * nandrow[0] = 1, and run the same check on the first row too. A block in the first row then cuts off the cells to its right.- How does the code change for Minimum Path Sum (LC 64)?
The cell holds the smallest cost of a path to it. The update becomes
row[j] = min(row[j], row[j - 1]) + cost. The first row has only a left neighbour, and the first column has only an upper neighbour, so those cells copy the one neighbour they have. The time and space stay the same.- Is there a faster way for plain Unique Paths (LC 62)?
Yes. The answer is the binomial coefficient C(m + n - 2, m - 1), the number of ways to place the
m - 1down moves among all moves. Form = 3andn = 7it is 28. It works only for an empty grid. The table is needed for obstacles or costs.
SWE Reasoning
Spot it
- A walker moves only right and down through a grid, from one corner to the opposite corner.
- You count the paths, find the cheapest path, or find the largest square of cells.
- The answer for a cell can be built from the cell above and the cell to its left.
- The grid has up to about 100 or 1000 cells per side, so
M * Ncells is fine, and trying every path is exponential. - The problem asks for one number, not for the paths listed.
The invariant, step by step
- Before the loop,
row = [1] * n. This is row 0. Each cell is reached one way, by moving right along the top edge. - The outer loop moves to the next row. At this moment
row[j]is the answer for the row above, for everyj. - Column 0 is not changed, because it has no left neighbour. It stays 1, as it is reached one way by moving down.
- For each
jfrom 1 ton - 1, the code runsrow[j] += row[j - 1].row[j]is the count from above, androw[j - 1]is the count from the left, already updated for this row. - After the inner loop,
row[j]is the answer for cell(i, j)for everyj, which is the card's invariant. - After the last row,
row[n - 1]is the answer for the bottom-right cell. The code returns it.
Traps
- Start
jat 0.row[j - 1]becomesrow[-1], the last cell. Python raises no error. On one column,unique_paths(5, 1)returns 16 instead of 1. - Start
rowas zeros. The first row then says that no path reaches any cell, and every count stays 0.unique_paths(3, 7)returns 0 instead of 28. - Fill the first row with 1 despite an obstacle. In Unique Paths II (LC 63), a blocked cell has 0 paths, and it also cuts off every cell to its right in the first row. Start with only
row[0] = 1, and apply the obstacle check to the first row too. - Use
maxor+in the wrong place. Counting paths adds the two neighbours. A cheapest path takes the smaller neighbour and then adds the cell's own cost. - Use the formula when cells are blocked or have costs. The binomial formula counts every path in an empty grid only.
Practice
Builds on Linear DP, which you haven’t finished yet.
2D DP: Grid Paths (Unique Paths, Minimum Path Sum)
Picture a robot dropped onto the top-left cell of an m x n grid, aiming for the bottom-right cell. On every move it can step either one cell down or one cell right -- nothing else.
Given the grid dimensions m and n, count how many distinct routes the robot could take from start to finish. You can assume the true count never exceeds 2 * 109.
3 x 7 grid.Grid DP
grid dp[i][j] ➔ depends on the cell above and the cell to the left ➔ 1D rolling row| 1 | def unique_paths(m: int, n: int) -> int: |
| 2 | """Unique Paths: count right/down paths in an m x n grid with one rolling row. |
| 3 | Time: O(M * N) | Space: O(N) |
| 4 | """ |
| 5 | # row: one rolling row of the DP grid; row[j] starts at 1 since row 0 is reached only by moving right |
| 6 | row = [1] * n |
| 7 | for _ in range(1, m): |
| 8 | for j in range(1, n): |
| 9 | # 1. Combine Above And Left: |
| 10 | # row[j] still holds the count from the row above; add row[j - 1], already updated for this row. |
| 11 | row[j] += row[j - 1] |
| 12 | return row[n - 1] |
i is filled, row[j] is the answer for grid cell (i, j) for every j.Give every grid cell (i, j) one answer, and build it only from the cell above and the cell to its left. Fill the grid row by row, so both cells are already final, and keep just one rolling row: row[j] still holds the answer from above when you add row[j - 1], the answer from the left. The trap is the first column: row[0] has no left neighbour and stays 1, so the inner loop must start at j = 1; starting at 0 reads row[-1], the last cell.
See it run
Unique Paths, step by step (3 by 3 grid)
row -row[n - 1] -
Row i is the list row after grid row i is filled. Column j is the grid column j.
newthe cell being writtenabovethe cell one row up, which is readleftthe cell one column to the left, which is readanswerthe final answer
Start: unique_paths(3, 3) counts the right and down paths in a grid with 3 rows and 3 columns.
Gotcha 1 of 3
- The trap
Gotcha 1: Starting
jat 0 inunique_pathsMistakefor j in range(0, n):Fixfor j in range(1, n):What happens: Column 0 is reached in exactly one way, so
row[0]must stay 1. Withj = 0, the line readsrow[-1], which is the last cell. Python raises no error. On one column,row[0] += row[0]doubles the cell on every row.Example: m = 5, n = 1Mistake: returns 16Fix: returns 1
- Two strings are compared prefix by prefix, so a cell also looks at the cell diagonally up and to the left, as in Edit Distance (LC 72), and there is no grid to walk through. See Two-Sequence DP
- The state is one range of a single sequence, built from shorter ranges inside it, as in Longest Palindromic Subsequence (LC 516), not a path from a corner of a grid. See Interval DP
Deep Dive
What one cell means
A grid DP gives every cell (i, j) one answer, and the answer is final once the cell is written. In unique_paths, row[j] after row i is the number of paths from the top-left corner to cell (i, j), when the walker moves only right or down.
The state is a pair of positions, so the number of states is the number of cells: M * N for a grid with M rows and N columns.
The same table shape works when the answer is not a count. In Minimum Path Sum (LC 64), a cell holds the smallest total cost of a path to it.
Why the recurrence is correct
A path that ends at cell (i, j) made its last move either down, from the cell above, or right, from the cell to the left. These two groups share no path, and together they contain every path. So the count is above + left, which the code writes as row[j] += row[j - 1].
The first row and the first column have only one neighbour. Each of their cells is reached in exactly one way, by moving along the edge. This is why row starts as [1] * n, and why the inner loop starts at j = 1.
Example: for m = 3 and n = 3, row is [1, 1, 1] at the start. After the second row it is [1, 2, 3]. After the third row it is [1, 3, 6], so unique_paths(3, 3) returns 6.
For Minimum Path Sum (LC 64), the sum is replaced by a minimum plus the cell's cost: row[j] = min(row[j], row[j - 1]) + cost. For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7.
Fill order and why one row is enough
Cell (i, j) reads only the cell above and the cell to the left. Both are final before the cell is computed, if rows are filled from top to bottom and each row from left to right.
Only the previous row is ever read. So one array row is enough. When the loop reaches row[j], that cell still holds the value of the row above. The cell row[j - 1] was already updated for the current row. Their sum is the paths from above plus the paths from the left.
This is why the space is O(N), the width of one row, and not O(M * N) for the whole grid.
The cost, a formula, and what blocks it
Each cell is computed once with constant work. So the time is O(M * N). For a 1000 by 1000 grid, that is one million cell updates. The space is O(N).
For plain Unique Paths (LC 62) there is also a closed formula. Every path has m - 1 down moves and n - 1 right moves. The number of paths is the number of ways to choose where the down moves go, which is C(m + n - 2, m - 1). For m = 3 and n = 7 it is 28, the same as unique_paths(3, 7).
The formula stops working when a cell is blocked, as in Unique Paths II (LC 63), or when a cell has a cost, as in Minimum Path Sum (LC 64). The table handles both, so it is the general tool.
60-Second Pitch
"A brute force tries every path, which takes exponential time. I define one cell (i, j) as the answer for the walker that stops there. A path ends with a move down or a move right, so the cell depends only on the cell above and the cell to the left. The first row and column are reached one way each, so I start with a row of ones. Then I fill row by row, and I add row[j - 1] to row[j]. There are M times N cells with constant work each, so the time is O(M * N). I keep one row, so the space is O(N)."
Common Questions
- What are the time and space complexity of
unique_paths? O(M * N) time, because each cell does constant work.
O(N)space, because the code keeps one row of widthN.- Why is a single row enough?
Each cell reads only the cell above and the cell to the left. When the loop reaches
row[j], it still holds the value from the row above, androw[j - 1]was already updated for the current row. No older row is read.- How does the code change for obstacles, as in Unique Paths II (LC 63)?
A blocked cell has 0 paths, so the code sets
row[j] = 0for it. Start withrow = [0] * nandrow[0] = 1, and run the same check on the first row too. A block in the first row then cuts off the cells to its right.- How does the code change for Minimum Path Sum (LC 64)?
The cell holds the smallest cost of a path to it. The update becomes
row[j] = min(row[j], row[j - 1]) + cost. The first row has only a left neighbour, and the first column has only an upper neighbour, so those cells copy the one neighbour they have. The time and space stay the same.- Is there a faster way for plain Unique Paths (LC 62)?
Yes. The answer is the binomial coefficient C(m + n - 2, m - 1), the number of ways to place the
m - 1down moves among all moves. Form = 3andn = 7it is 28. It works only for an empty grid. The table is needed for obstacles or costs.
SWE Reasoning
Spot it
- A walker moves only right and down through a grid, from one corner to the opposite corner.
- You count the paths, find the cheapest path, or find the largest square of cells.
- The answer for a cell can be built from the cell above and the cell to its left.
- The grid has up to about 100 or 1000 cells per side, so
M * Ncells is fine, and trying every path is exponential. - The problem asks for one number, not for the paths listed.
The invariant, step by step
- Before the loop,
row = [1] * n. This is row 0. Each cell is reached one way, by moving right along the top edge. - The outer loop moves to the next row. At this moment
row[j]is the answer for the row above, for everyj. - Column 0 is not changed, because it has no left neighbour. It stays 1, as it is reached one way by moving down.
- For each
jfrom 1 ton - 1, the code runsrow[j] += row[j - 1].row[j]is the count from above, androw[j - 1]is the count from the left, already updated for this row. - After the inner loop,
row[j]is the answer for cell(i, j)for everyj, which is the card's invariant. - After the last row,
row[n - 1]is the answer for the bottom-right cell. The code returns it.
Traps
- Start
jat 0.row[j - 1]becomesrow[-1], the last cell. Python raises no error. On one column,unique_paths(5, 1)returns 16 instead of 1. - Start
rowas zeros. The first row then says that no path reaches any cell, and every count stays 0.unique_paths(3, 7)returns 0 instead of 28. - Fill the first row with 1 despite an obstacle. In Unique Paths II (LC 63), a blocked cell has 0 paths, and it also cuts off every cell to its right in the first row. Start with only
row[0] = 1, and apply the obstacle check to the first row too. - Use
maxor+in the wrong place. Counting paths adds the two neighbours. A cheapest path takes the smaller neighbour and then adds the cell's own cost. - Use the formula when cells are blocked or have costs. The binomial formula counts every path in an empty grid only.