Problem overview
The function unique_paths receives a grid of 0s and 1s, a Vec<Vec<i32>> with n rows and m columns. A 0 is an empty cell and a 1 is an obstacle. A robot starts at the top-left cell and must reach the bottom-right cell, moving only down or right. The function returns the number of different paths that avoid every obstacle.
In the example, the 3x3 grid has one obstacle in the middle. Two paths exist: right, right, down, down along the top and right edges, and down, down, right, right along the left and bottom edges. The answer is 2.
Approach: count the ways into each cell
Enumerating paths one by one would take exponential time. Count them instead. Let dp[i][j] be the number of paths from the start to cell (i, j). A path enters a cell either from the cell above or from the cell to its left, and those are different paths, so for an empty cell:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]A cell with an obstacle can't be stood on, so its count stays 0. The first row and first column are special because they have only one neighbour. A cell in the first column can only be reached by going straight down, so it has exactly one path, unless an obstacle sits above it or on it. Then it and every cell below it has none. The first row works the same way from left to right.
The cells are filled so that both neighbours are always known when they are needed: first the edges, then the rest row by row.
Step by step
- Read the dimensions:
nisgrid.len()andmisgrid[0].len(). - Create
dpas a mutablenbymgrid ofi32zeros, usingvec!twice. - Fill the first column. Loop
iover0..n. - Stop at an obstacle. If
grid[i][0]is 1,break: this cell and all below it keep their 0. - Otherwise set
dp[i][0] = 1. A free cell in the first column has exactly one path. - Fill the first row with a loop over
jin0..m. - Stop at an obstacle in the first row with
break. - Set
dp[0][j] = 1for free cells. The start cell is set twice, which is harmless. - Fill the rest with two nested loops,
iover1..nandjover1..m. - Skip obstacles. Only when
grid[i][j] == 0, apply the recurrence. - Return the bottom-right cell,
dp[n - 1][m - 1].
The solution in Rust
impl Solution {
fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut dp = vec![vec![0i32; m]; n];
for i in 0..n {
if grid[i][0] == 1 {
break;
}
dp[i][0] = 1;
}
for j in 0..m {
if grid[0][j] == 1 {
break;
}
dp[0][j] = 1;
}
for i in 1..n {
for j in 1..m {
if grid[i][j] == 0 {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
dp[n - 1][m - 1]
}
}
The Rust details worth knowing:
- Vectors of vectors.
grid[i][j]first indexes the outer vector to get rowi, then indexes that row. The grid arrives by value, so the function owns it and can read it freely. len()is ausize. Sonandmareusizeand the loop variablesiandjbecomeusizetoo, which is exactly what indexing needs. No casts are required.vec![row; n]clones the row. Each of thenrows is a separate vector, so writingdp[1][0]doesn't also changedp[0][0].break. It leaves the innermost loop immediately. Here that is the first-column or first-row loop, and it works because everything past an obstacle in an edge is unreachable.- Subtracting from
usize.i - 1andj - 1are safe because both loops start at 1. At 0 they would underflow, which panics in a debug build and wraps in an optimized one. - Overflow. The count can grow quickly on big empty grids. The lesson guarantees the answer fits in an
i32. Counts for cells that can't reach the finish aren't covered by that guarantee, and in an optimized build they would wrap silently without affecting the answer.
Complexity
Time: O(n * m). Each cell is filled once with a constant amount of work.
Space: O(n * m). The dp table is the same size as the grid. A single row kept and updated in place would reduce this to O(m).
Edge cases and common mistakes
- Blocked start or finish.
[[1, 0], [0, 0]]and[[0, 0], [0, 1]]both give 0. A blocked start stops both edge loops at their first step, and a blocked finish is never filled, so it stays 0. - A single cell.
[[0]]gives 1: the robot is already there. The loops over1..nand1..mare empty. - A single row or column.
[[0, 1]]gives 0, and[[0], [0]]gives 1. - An obstacle that blocks an edge. In
[[0, 1], [0, 0]], the first row stops at column 1. The path must go down first, so the answer is 1. If the edge loop didn'tbreakand kept setting 1 after the obstacle, cells beyond it would be counted as reachable. - Forgetting to skip obstacles in the interior. Applying the recurrence to a 1-cell would give it paths that can't exist.
- An empty grid. The function reads
grid[0], so a vector with no rows panics. The lesson's inputs always have at least one row.
Testing
[[0,0,0],[0,1,0],[0,0,0]]gives2.[[0,0,0],[0,0,0],[0,0,0]]gives6.[[0,0],[1,0]]gives1.[[0,0],[0,1]]gives0.[[0]]gives1.
