Problem overview
A robot stands in the top-left cell of a grid and wants to reach the bottom-right cell. It can only move down or right. Some cells hold obstacles. In C#, the grid is an int[,] passed to UniquePaths(int[,] grid), where 1 marks an obstacle and 0 an empty cell. The method returns the number of different paths from corner to corner.
The example is a 3x3 grid with a single obstacle in the center. Two paths exist: right, right, down, down, and down, down, right, right. The answer fits in a 32-bit int, as the problem guarantees, and the grid has at most 100 rows and 100 columns.
Approach: count the ways into each cell
Listing every path is hopeless: a 100x100 grid has an astronomical number of them. Count them instead. 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 or from the cell to the left. Every path to (i, j) therefore ends with one of those two moves, and the two groups of paths never overlap. So for an empty cell:
dp[i, j] = dp[i - 1, j] + dp[i, j - 1]
An obstacle cell has no paths through it, so its count stays 0. The first row and column are special because they have only one neighbour: each cell can be reached in exactly one way, unless an obstacle cuts the line earlier.
For the example, the finished table is:
1 1 1
1 0 1
1 1 2
The bottom-right value, 2, is the answer.
Step by step
- Read the size. A rectangular array has no single
Lengthfor rows or columns, so usegrid.GetLength(0)for the rows (n) andgrid.GetLength(1)for the columns (m). - Create the table
dpas anint[n, m]. C# starts every cell at 0. - Fill the first column. Walk down from row 0. At the first obstacle,
break: that cell and everything below it can't be reached through the column, so they keep 0. Otherwise set the cell to 1. - Fill the first row the same way, walking right and stopping at the first obstacle. If the start itself is blocked, both loops break at once, and every cell stays 0.
- Fill the rest with two nested loops from 1, row by row. By the time a cell is reached, the cells above and to the left are done.
- Skip obstacles. Only when
grid[i, j] == 0is the cell set to the sum of its two neighbours. - Return
dp[n - 1, m - 1]. If the target is an obstacle, it was never written and the answer is 0.
The solution in C#
class Solution {
public int UniquePaths(int[,] grid) {
int n = grid.GetLength(0);
int m = grid.GetLength(1);
int[,] dp = new int[n, m];
for (int i = 0; i < n; ++i) {
if (grid[i, 0] == 1) {
break;
}
dp[i, 0] = 1;
}
for (int j = 0; j < m; ++j) {
if (grid[0, j] == 1) {
break;
}
dp[0, j] = 1;
}
for (int i = 1; i < n; ++i) {
for (int 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];
}
}
Some C# details:
- Two indexes in one pair of brackets. A rectangular
int[,]is indexed asgrid[i, j]. The jagged formgrid[i][j]belongs toint[][], a different type. Lengthcounts all cells. For a 3x4 arraygrid.Lengthis 12. UseGetLength(0)andGetLength(1)for the sizes of each dimension.- The corner is written twice. If the start is free, both the column loop and the row loop set
dp[0, 0]to 1. The second write changes nothing. - Zeros do the work for blocked cells. No
elseis needed, because the table is zero-filled and an unwritten cell already holds the right value.
Complexity
Time: O(n * m). Each cell is filled once with constant work.
Space: O(n * m). The table is as big as the grid. Each row depends only on the one above, so a single row of length m could replace it.
Edge cases and common mistakes
- Blocked start or finish.
{{1, 0}, {0, 0}}gives 0 because the robot cannot even begin, and{{0, 0}, {0, 1}}gives 0 because it cannot end. - A single cell.
{{0}}gives 1: the robot is already at the finish.{{1}}gives 0. - A blocked first row or column.
{{0, 1}, {0, 0}}gives 1: only the route down then right is open. Forgetting thebreakwould let cells behind an obstacle count a path that jumps over it. - Treating the obstacle as 1 path. The obstacle cell must stay 0. Setting it to 1 would count paths through it.
- Starting the main loops at 0. Row 0 and column 0 have no cell above or to the left, so the recurrence would read index -1 and throw
IndexOutOfRangeException. - Swapping the dimensions.
GetLength(0)is rows andGetLength(1)is columns. A grid with 2 rows and 3 columns hasGetLength(0)equal to 2.
Testing
- The 3x3 grid with a center obstacle gives 2.
- A 2x2 grid of zeros gives 2.
{{0, 1}, {0, 0}}gives 1.{{1, 0}, {0, 0}}gives 0.{{0}}gives 1.