Problem overview
The method uniquePaths(grid) receives an n by m grid of 0s and 1s. A robot starts at the top-left cell and wants to reach the bottom-right cell, moving only down or right. A 0 is an empty cell and a 1 is an obstacle the robot can't enter. The method returns the number of different paths.
In the example the grid is 3 by 3 with one obstacle in the middle. The two paths are right, right, down, down and down, down, right, right. Every other route would have to cross the center cell, and the obstacle blocks it. The notes limit both dimensions to 100 and promise that the answer fits in a 32-bit integer.
Approach: count the ways into each cell
Enumerating paths one at a time gets out of hand quickly: an open 18 by 18 grid already has over two billion of them. The better idea is to count paths cell by cell.
Let dp[i][j] be the number of paths from the start to cell (i, j). The robot can enter a cell only from the cell above it or the cell to its left, so for a free cell:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
An obstacle cell has no paths through it, so it stays at 0. This also does the right thing for its neighbors: they simply receive 0 from that direction.
The first row and the first column have only one neighbor, so they are set up separately. Every cell in the first column can be reached in exactly one way, straight down, unless an obstacle appears above it. Once the robot's only route is cut, every cell below is unreachable and stays 0. The first row works the same way going right.
For the example grid, the table comes out as:
1 1 1
1 0 1
1 1 2
The bottom-right value, 2, is the answer.
Step by step
- Read the dimensions.
nisgrid.length(rows) andmisgrid[0].length(columns). - Create the table of
nrows withmzeros each. - Fill the first column. Go down from row 0. At the first obstacle, stop; otherwise set the cell to 1.
- Fill the first row. Go right from column 0 with the same rule. The start cell is written by both loops, which is harmless.
- Fill the rest row by row, starting at row 1 and column 1, so the cells above and to the left are always ready.
- Skip obstacles. Only compute a cell when
grid[i][j]is 0. - Apply the recurrence for free cells.
- Return the bottom-right cell. If it is an obstacle, it is still 0, which is the right answer.
The solution in TypeScript
class Solution {
uniquePaths(grid: number[][]): number {
let n = grid.length;
let m = grid[0].length;
let dp: number[][] = Array.from({ length: n }, () => new Array(m).fill(0));
for (let i = 0; i < n; ++i) {
if (grid[i][0] == 1) {
break;
}
dp[i][0] = 1;
}
for (let j = 0; j < m; ++j) {
if (grid[0][j] == 1) {
break;
}
dp[0][j] = 1;
}
for (let i = 1; i < n; ++i) {
for (let j = 1; j < m; ++j) {
if (grid[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[n - 1][m - 1];
}
}
TypeScript details worth knowing:
- Building a 2D array safely.
Array.from({ length: n }, () => new Array(m).fill(0))calls the arrow function once per row, so each row is a different array. The temptingnew Array(n).fill(new Array(m).fill(0))stores one row object in allnslots. Settingbad[0][0] = 1on such a table with two rows prints[ [ 1, 0 ], [ 1, 0 ] ]: both rows changed. fill(0)is needed. A barenew Array(m)holds empty slots, and adding to one givesNaN.==versus===. The lesson compares with==, which converts types when they differ. Here both sides are numbers, so it behaves like===, which is the safer default.breakleaves the nearest loop. It ends only the loop it is in. The cells it skips keep their initial 0.- No overflow. A
numberis a double. The count stays exact up to 2^53, well beyond the 32-bit limit the notes mention. An open 18 by 18 grid gives 2333606220, which wouldn't fit in a 32-bit integer but is exact here.
Complexity
Time: O(n * m). Each cell is computed once with a constant amount of work.
Space: O(n * m). The table is the same size as the grid. Because each row needs only the row above, a single row would be enough.
Edge cases and common mistakes
- Blocked start. If
grid[0][0]is 1, both setup loops break at once. Nothing is reachable and the answer is 0. This works because the recurrence then adds only zeros. - Blocked finish. The last cell is skipped by the
== 0test and stays 0. - A blocked first column.
[[0], [1], [0]]returns 0: the middle obstacle cuts off the last cell. - Single cell.
[[0]]returns 1, the empty path, and[[1]]returns 0. - Single row.
[[0, 0, 0, 0]]returns 1. - Not breaking on an obstacle. Without
break, the cells after the obstacle in the first row would still get a 1, as if the robot could jump over it. - Empty grid.
grid[0].lengththrows aTypeErrorwhengridis[], sincegrid[0]isundefined. The lesson doesn't ask for it.
Testing
[[0,0,0],[0,1,0],[0,0,0]]gives2.[[0,0],[0,0]]gives2.[[0,1],[1,0]]gives0.[[1,0],[0,0]]gives0.[[0],[1],[0]]gives0.