Paths in a grid
In the frog, stairs and coin problems, every state was a position in a row: a stone, a step, an amount of money. In this lesson the input is a grid, and each state is one of its cells. The problems are about paths. A path starts in the top-left cell, moves one cell to the right or one cell down at each step, and ends in the bottom-right cell. The first problem asks how many paths there are.
A robot stands in the top-left cell of a grid with rows and columns and wants to reach the bottom-right cell. Each move takes it one cell right or one cell down.
Return the number of different paths the robot can take.
Constraints
- The answer is at most
Sample 1 · Input
m = 3, n = 7
Output
28
Sample 2 · Input
m = 3, n = 2
Output
3
In the second sample the grid has 3 rows and 2 columns. Every path makes two moves down and one move right, and the three paths differ only in when the move right happens:
- right, down, down
- down, right, down
- down, down, right
A program could count the paths by generating them one at a time, but there are too many. In a grid with rows and columns, every path makes moves down and moves right, so a path is fixed once we say which of its moves go down. A grid of 17 rows and 17 columns, well inside the limits, has 32 moves on every path, and there are 601,080,390 ways to choose the 16 that go down. Instead, we compute one number for each cell, the number of paths that reach it, and that grid has only cells.
For this problem the choice of moves also gives a formula, . The cell-by-cell method gives the same numbers, and unlike the formula it still works later in the lesson, when some cells are blocked.
Build the transition from the last move
As with the frog, we ask one smaller question for each place a path can pass through. Let dp[r][c] be the number of paths from the top-left cell to the cell in row and column , where rows and columns are numbered from 0. Each state is a cell, so the table has the same shape as the grid, and the answer is the entry for the bottom-right cell, dp[m - 1][n - 1].
For the transition, look at the last move of a path that ends on cell . It was a move down from the cell above, , or a move right from the cell to the left, . So every path into is a path into one of those two cells followed by one more move. A path has only one last move, so no path is counted for both cells, and the count for is the count for the cell above plus the count for the cell to the left. This is the Climbing Stairs transition with two neighbouring cells in place of the two steps below:
The cells of the top row have no cell above them, and the cells of the left column have no cell to their left, so they are the base cases. A cell in the top row can only be reached by moving right along that row, and a cell in the left column only by moving down that column. Each of them has exactly 1 path. So does the start cell, whose one path makes no moves.
The evaluation order comes from what the transition reads: an entry in the row above and an earlier entry in the same row. If we fill the table one row at a time from the top, and each row from left to right, both are stored before the entry that needs them.
Here is the finished table for the first sample, a grid of 3 rows and 7 columns:
The top row and the left column hold 1s. The entry in row 2 and column 4 has a 5 above it and a 10 to its left, so it is 15. The bottom-right entry is 28, the expected output.
The program starts every entry at 1, which sets the top row and the left column, and then fills the other entries in the order described:
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
for c in range(1, n):
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
return dp[m - 1][n - 1]
print(unique_paths(3, 7))
print(unique_paths(3, 2))Prints 28 and 3, the two samples.
The table has entries and each one takes at most one addition, so the largest input, 100 rows and 100 columns, needs fewer than 10,000 additions.
Paths around blocked cells
In a harder version of this problem, some cells are blocked and a path may not enter them. Suppose the grid is given as rows of characters, where . is a free cell and # is a blocked one, and we still want the number of paths from the top-left cell to the bottom-right cell.
The states are the same cells, and the transition gets one more case. No path ends on a blocked cell, so its entry is 0. A free cell adds the entries above it and to its left as before, and a blocked neighbour contributes its 0:
The top row and the left column can no longer be set to 1 in advance. A blocked cell in the top row cuts off every cell to its right, because the only way along the top row is through it, and the same happens below a blocked cell in the left column. It is simpler to keep a single base case, the start cell with its 1 path, and to let every other free cell add whichever of its two neighbours exist. A neighbour outside the grid counts as 0 paths.
Here is a grid with two blocked cells, beside its table:
The top row reads 1, 1, 0, 0: the blocked cell and the cell after it cannot be reached along the row. The last cell of row 1 has no paths arriving from above, but 2 arrive from its left. The bottom-right cell ends with 4 paths.
def count_paths(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if grid[r][c] == "#":
dp[r][c] = 0
elif r == 0 and c == 0:
dp[r][c] = 1
else:
above = dp[r - 1][c] if r > 0 else 0
left = dp[r][c - 1] if c > 0 else 0
dp[r][c] = above + left
return dp[rows - 1][cols - 1]
print(count_paths(["..#.", "....", ".#.."]))
print(count_paths([".......", ".......", "......."]))Prints 4 for the grid above and 28 for a grid of 3 rows and 7 columns with no blocked cells.
The second call is the first sample of Unique Paths written as a grid, and it gives 28 again. A blocked start cell needs no code of its own: its entry is 0, and every other entry is then a sum of 0s.
These counts grow quickly with the grid. A grid of 1,000 rows and 1,000 columns with no blocked cells has a number of paths 600 digits long. Problems on large grids therefore ask for the count modulo a prime such as , and a program for them takes the remainder after every addition. The final remainder is still the right one, because the remainder of a sum depends only on the remainders of its parts.
The cheapest path through a grid
The entries so far were counts. When every cell has a cost and we want the cheapest path, the same states hold a minimum, as the frog's table did.
A grid with rows and columns holds nonnegative numbers. Move from the top-left cell to the bottom-right cell, one cell right or down at a time.
Return the smallest possible sum of the numbers on the path, counting both end cells.
Constraints
- Every number is between 0 and 200
Sample 1 · Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Sample 2 · Input
grid = [[1,2,3],[4,5,6]]
Output
12
In the first sample the cheapest path runs along the top row and then down the right column:
Let dp[r][c] be the smallest sum of a path from the top-left cell to cell , with both of those cells counted. The last move into again comes from above or from the left. Suppose it comes from above. The earlier part of the path is then a path to the cell above, and cell adds the same cost to every such path, so the best choice is the cheapest of them, which costs dp[r - 1][c]. The same goes for the cell to the left. That leaves two candidates, and the transition keeps the smaller:
The start cell is the base case, and its entry is its own cost. A cell in the top row has only a left neighbour, and a cell in the left column only one above. When we counted paths, a neighbour outside the grid counted as 0. A 0 would be wrong here, because the minimum would pick it. The missing neighbour has to lose every comparison, so the program gives it the value infinity.
For the first sample the table is:
The entry in the middle is : the middle cell costs 5, the cheapest way to the cell above it costs 4, and the cheapest way to the cell on its left costs 2. The bottom-right entry is , the expected output.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[float("inf")] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
dp[r][c] = grid[r][c]
continue
up = dp[r - 1][c] if r > 0 else float("inf")
left = dp[r][c - 1] if c > 0 else float("inf")
dp[r][c] = grid[r][c] + min(up, left)
return dp[-1][-1]
print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
print(min_path_sum([[1, 2, 3], [4, 5, 6]]))Prints 7 and 12, the two samples.
At the problem's limits the table has entries, and each takes one comparison and one addition.
Rebuild the path from the table
The table gives the cost of the cheapest path and not the path. For the frog we stored a parent for every stone. Here the table already holds what a parent array would: the last move into a cell came from whichever neighbour has the smaller entry. So the walk starts at the bottom-right cell and keeps stepping to the smaller of the entry above and the entry to the left until it reaches the start. When the two are equal, either will do, since both lie on a cheapest path. That collects the path backwards in steps.
In the table above, the walk starts at the bottom-right 7. The entry above it is 6 and the entry to its left is 8, so it steps up, and then up again to the 5. In the top row the only way is left, to the 4 and the 1. Those are the highlighted entries.
The widget fills the same table one entry at a time, with each cell's own cost in its corner, and on its last step walks back along the cheapest path. The costs can be edited. If the 3 in the top row becomes a 9, the cheapest cost rises to 9, and two paths have that cost, both starting with a move down.
The largest square of 1s
A state that is a cell does not have to describe a path. In the next problem each state describes a shape that ends at its cell, the way the longest-increasing-subsequence table described a subsequence that ends at each position.
A grid with rows and columns holds the characters "0" and "1".
Return the area of the largest square that contains only "1"s.
Constraints
Sample 1 · Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output
4
Sample 2 · Input
matrix = [["0","1"],["1","0"]]
Output
1
Sample 3 · Input
matrix = [["0"]]
Output
0
In the first sample, with rows and columns numbered from 0, rows 1 and 2 hold two overlapping 2 by 2 blocks of 1s: one in columns 2 and 3, and the one highlighted below in columns 3 and 4. No 3 by 3 block of 1s exists, so the answer is 4:
Checking every square directly is too slow. A grid of 300 rows and 300 columns contains 9,045,050 squares of all sizes and positions, and reading the cells of each one adds up to about reads.
Let side[r][c] be the side length of the largest square of 1s whose bottom-right corner is cell . If the cell holds a 0, no such square exists and the entry is 0. If it holds a 1, the entry depends on three neighbours: the cell above, the cell to the left, and the cell diagonally up and to the left.
Suppose a square of side ends at . Remove its bottom row and its right column, and what remains is a square of side that ends at the diagonal neighbour. In the same way, the square without its bottom row and left column ends at the cell above, and the square without its top row and right column ends at the cell to the left. So each of the three neighbours has an entry of at least , which means is at most 1 more than the smallest of the three entries.
This bound is always reached. Call the smallest of the three entries . A square of 1s of side then ends at each of the three neighbours, and these three squares cover every cell of the square of side that ends at , except itself, which holds a 1. The left half of the figure below shows this for . So for a cell that holds a 1,
In the table on the right, the entry in row 2 and column 3 has a 1 above it, a 1 to its left and a 1 on its diagonal, so it is 2. The entry after it, in column 4, has a 2 to its left but only 1s above it and on its diagonal, so it is 2 as well and not 3.
In the first row and the first column, a neighbour outside the grid counts as 0, which is right for a square that cannot extend past the edge. The program gets those 0s from an extra row and an extra column at the top and left of the table, so the entry for grid cell is stored at side[r + 1][c + 1]. The largest square can end at any cell, so the program keeps the largest entry it has seen, and the problem asks for the area, which is that side squared.
def maximal_square(matrix):
rows, cols = len(matrix), len(matrix[0])
side = [[0] * (cols + 1) for _ in range(rows + 1)]
best = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == "1":
side[r + 1][c + 1] = 1 + min(side[r][c + 1],
side[r + 1][c],
side[r][c])
best = max(best, side[r + 1][c + 1])
return best * best
print(maximal_square(["10100", "10111", "11111", "10010"]))
print(maximal_square(["01", "10"]))
print(maximal_square(["0"]))Prints 4, 1 and 0, the three samples.
LeetCode passes each row as a list of one-character strings. The listing takes each row as a string, which is indexed the same way.
Time and space of grid tables
- Counting paths, with or without blocked cells
time and space - One state per cell with two candidates each: 10,000 entries for a grid of 100 rows and 100 columns.
- Cheapest path
time and space - The same states with a minimum: 40,000 entries at the limits of Minimum Path Sum.
- Rebuilding the path
steps - One step per move of the path. The walk reads the finished table, so every row has to be kept.
- Largest square
time and space - One state per cell with three neighbours each. With its extra row and column the table has entries at the limits.
Every transition in this lesson reads the row above and the current row, and nothing older. A program that needs only the final value can therefore keep the last row or two and drop the rest, which saves memory but gives up the walk back. The next lesson, Knapsack, has a table where that saving is needed.
Common mistakes
Starting the top row and the left column at 1 when some cells are blocked.
- Where it breaks
- On the grid
["..#.", "....", ".#.."], a program that starts every entry at 1 and applies the blocked-cell transition from row 1 and column 1 onward leaves the top row at 1, 1, 1, 1 and returns7. The answer is4: the last two cells of the top row cannot be reached. - The fix
- Give only the start cell a 1, and let every other free cell add the neighbours that exist.
Treating a neighbour outside the grid as 0 in the cheapest-path table.
- Where it breaks
- On
[[1,3,1],[1,5,1],[4,2,1]], a table with an extra row and column of 0s lets every cell of the top row and the left column take the 0 from outside, and the bottom-right entry comes out as3. The answer is7. - The fix
- Give a missing neighbour the value infinity in a minimum, and give only the start cell its own cost.
Leaving the diagonal neighbour out of the square transition.
- Where it breaks
- On
["01", "11"], the bottom-right cell has a 1 above it and a 1 to its left, so a minimum over those two alone gives side 2 and area4. The top-left cell holds a 0, and the answer is1. - The fix
- Take the minimum over all three neighbours: above, left and diagonal.
Recall Suppose the robot in Unique Paths may also move diagonally, one cell down and one cell right in a single move. How does the transition change, and does the evaluation order still work?
A path into cell now ends with one of three moves, so the entry is the sum of three neighbours: the cell above, the cell to the left, and the cell diagonally up and to the left. The top row and the left column still hold 1s: a diagonal move ends one row lower and one column further right than it starts, so it cannot end in the top row or the left column.
The diagonal neighbour is in the row above, like the cell straight above, and that whole row is filled before the current one. So filling row by row, each row from left to right, still has every entry ready. For the grid of 3 rows and 2 columns the count rises from 3 to 5.