63. Unique Paths II
Problem Description
You are presented with a grid represented by an m x n
integer array called grid
. This grid is filled with either 0's or 1's, which denote empty spaces and obstacles, respectively. There is a robot situated at the top-left corner of the grid, i.e., at grid[0][0]
. The goal for the robot is to reach the bottom-right corner of the grid, namely grid[m - 1][n - 1]
.
The robot can only move in two directions at any given time: either down or to the right. Given these movement restrictions and the presence of obstacles (denoted by 1's), the task is to calculate the number of unique paths the robot can take to reach its destination without traversing any of the obstacles.
To provide a solution, the assumption is made that the number of unique paths will not exceed 2 * 10^9
.
Intuition
When thinking about the robot's journey from the top-left to the bottom-right corner, we can frame the problem using dynamic programming. The approach focuses on the concept that the number of ways to reach a particular cell in the grid is the sum of the ways to reach the cell directly above it and the cell to its immediate left, since the robot can only move down or right.
However, when a cell contains an obstacle, the robot cannot travel through it, which means this cell contributes zero paths to its adjacent cells.
Here's a breakdown of the dynamic programming solution:
- Start by initializing a 2D array
dp
(same dimensions asgrid
) to store the number of ways to reach each cell. - Set the value of
dp[i][0]
(first column) anddp[0][j]
(first row) to 1 for as long as there are no obstacles. This represents the fact that there is only one way to move along the top row or the leftmost column when there are no obstacles in those positions. - Loop through the grid starting from cell
dp[1][1]
and move rightward and downward. - For every cell, check if it is not an obstacle. If it isn't, set
dp[i][j]
to the sum ofdp[i - 1][j]
(the number of ways to reach from above) anddp[i][j - 1]
(the number of ways to reach from the left). - If you encounter an obstacle, set the number of ways to 0 because the robot can't pass through obstacles.
- Continue this process until you reach the bottom-right corner of the grid.
- The final answer, the number of unique paths to the bottom-right corner avoiding obstacles, will be found in
dp[m-1][n-1]
.
With this approach, we can systematically compute the number of unique paths available to the robot, taking into consideration the positioning of the obstacles.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution approach for the problem is based on dynamic programming, a method for solving complex problems by breaking them down into simpler subproblems. It is a powerful technique for optimization problems like this, where we aim to count all possible unique paths in a grid with obstacles.
-
Data Structure: A 2-dimensional list
dp
of sizem x n
(wherem
andn
are the dimensions of the inputgrid
) is initialized with zeros. Thisdp
list is used to store the number of unique paths to reach each cell (i, j) from the start (0, 0). -
Base Cases Initialization: The robot can only move down or right. Therefore, if there are no obstacles in the first column and first row, there will be only one path to each of those cells — just keep moving right or down respectively.
1for i in range(m): 2 if obstacleGrid[i][0] == 1: 3 break 4 dp[i][0] = 1 5 6for j in range(n): 7 if obstacleGrid[0][j] == 1: 8 break 9 dp[0][j] = 1
These loops set the base conditions for the first row and column, stopping whenever an obstacle is encountered, since there would be no paths passing through the obstacle.
-
Dynamic Programming Loop: Starting from the cell (1, 1), the algorithm iteratively computes the number of paths to each cell, adding the number of paths from the cell directly above and the number of paths from the cell to the left, as long as those cells are not obstacles.
1for i in range(1, m): 2 for j in range(1, n): 3 if obstacleGrid[i][j] == 0: 4 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
This code is the heart of our dynamic programming approach. It succinctly captures the essence that at each step, the robot could have come from the left cell or the cell above.
-
Construct the Return Value: The value at
dp[m-1][n-1]
will be the total number of unique paths from the start to the bottom-right corner. It accounts for all possible paths that the robot could take without hitting an obstacle.1return dp[-1][-1]
In terms of time and space complexity, this algorithm runs in O(m * n), where m
and n
are the dimensions of the input grid, since we have to visit each cell once to calculate the number of paths to it. Space complexity is also O(m * n) due to the additional dp
list used to store the number of paths to each cell.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the dynamic programming approach described in the solution.
Consider the following grid grid
where 0
denotes an empty space and 1
denotes an obstacle:
1grid = [ 2 [0, 0, 0], 3 [0, 1, 0], 4 [0, 0, 0] 5]
We aim to calculate the number of unique paths from grid[0][0]
to grid[2][2]
.
-
Data Structure Initialization: Initialize the
dp
array with zeros.1dp = [ 2 [0, 0, 0], 3 [0, 0, 0], 4 [0, 0, 0] 5]
-
Base Cases Initialization: Populate the first row and first column as per the approach, considering the obstacles.
After initialization:
1dp = [ 2 [1, 1, 1], 3 [1, 0, 0], 4 [1, 0, 0] 5]
The obstacle in
grid[1][1]
means the robot cannot go through it, so we leavedp[1][1]
as0
. -
Dynamic Programming Loop: We compute the values of the remaining cells.
For
dp[1][2]
: Since the cell above it (dp[1][1]
) is blocked by an obstacle, we only add the paths from the left (dp[1][1]
), resulting indp[1][2] = 1
.For
dp[2][1]
: Similar to the previous, we only add the paths from the above (dp[1][1]
is 0 due to the obstacle) and the left (dp[2][0]
is 1), resulting indp[2][1] = 1
.Recalculated
dp
after iteration:1dp = [ 2 [1, 1, 1], 3 [1, 0, 1], 4 [1, 1, 0] 5]
For
dp[2][2]
: We add the values from above (dp[1][2] = 1
) and the left (dp[2][1] = 1
), giving usdp[2][2] = 2
.Final
dp
array:1dp = [ 2 [1, 1, 1], 3 [1, 0, 1], 4 [1, 1, 2] 5]
-
Construct the Return Value: The value at
dp[2][2]
is 2, signifying there are two unique paths from start to destination that avoid the obstacles.
Therefore, for the given grid, the robot has exactly two unique paths to reach the destination from the starting point.
Solution Implementation
1class Solution:
2 def uniquePathsWithObstacles(self, obstacle_grid: List[List[int]]) -> int:
3 # Get the number of rows and columns in the obstacle grid.
4 rows, cols = len(obstacle_grid), len(obstacle_grid[0])
5
6 # Initialize the DP (Dynamic Programming) table with zeros.
7 dp_table = [[0] * cols for _ in range(rows)]
8
9 # Set the value for the first cell to 1 if it is not an obstacle.
10 if obstacle_grid[0][0] == 0:
11 dp_table[0][0] = 1
12
13 # Populate the first column of the DP table.
14 for i in range(1, rows):
15 if obstacle_grid[i][0] == 0: # If there is no obstacle,
16 dp_table[i][0] = dp_table[i-1][0] # Use value from cell above.
17
18 # Populate the first row of the DP table.
19 for j in range(1, cols):
20 if obstacle_grid[0][j] == 0: # If there is no obstacle,
21 dp_table[0][j] = dp_table[0][j-1] # Use value from cell to the left.
22
23 # Fill in the rest of the DP table.
24 for i in range(1, rows):
25 for j in range(1, cols):
26 if obstacle_grid[i][j] == 0: # If the current cell is not an obstacle,
27 dp_table[i][j] = dp_table[i-1][j] + dp_table[i][j-1] # Sum of top and left cells.
28
29 # The bottom-right cell of the DP table will hold the number of unique paths.
30 return dp_table[-1][-1]
31
1class Solution {
2
3 // Function to calculate the unique paths in a grid with obstacles
4 public int uniquePathsWithObstacles(int[][] obstacleGrid) {
5 // Get the dimensions of the grid
6 int numRows = obstacleGrid.length;
7 int numCols = obstacleGrid[0].length;
8
9 // Initialize a DP table with dimensions equivalent to the obstacle grid
10 int[][] dp = new int[numRows][numCols];
11
12 // Set up the first column of the DP table. If there is an obstacle,
13 // paths beyond that point are not possible, so the loop will break.
14 for (int row = 0; row < numRows && obstacleGrid[row][0] == 0; ++row) {
15 dp[row][0] = 1;
16 }
17
18 // Set up the first row of the DP table. If there is an obstacle,
19 // paths beyond that point are not possible, so the loop will break.
20 for (int col = 0; col < numCols && obstacleGrid[0][col] == 0; ++col) {
21 dp[0][col] = 1;
22 }
23
24 // Iterate over the grid starting from cell (1, 1) to calculate the
25 // number of unique paths to each cell, considering the obstacles.
26 for (int row = 1; row < numRows; ++row) {
27 for (int col = 1; col < numCols; ++col) {
28 // If the current cell is not an obstacle
29 if (obstacleGrid[row][col] == 0) {
30 // Number of paths to current cell is the sum of paths to the
31 // cell above it and the cell to the left of it.
32 dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
33 }
34 // If the current cell is an obstacle, dp[row][col] remains 0
35 }
36 }
37
38 // Return the number of unique paths to the bottom-right corner of the grid
39 return dp[numRows - 1][numCols - 1];
40 }
41}
42
1class Solution {
2public:
3 // Method calculates the number of unique paths from top-left to bottom-right in
4 // a grid that may have obstacles. An obstacle and space are marked as 1 and 0, respectively, in the grid.
5 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
6 int numberOfRows = obstacleGrid.size(); // Get the number of rows in the grid.
7 int numberOfColumns = obstacleGrid[0].size(); // Get the number of columns in the grid.
8
9 // Create a 2D dp matrix with the same dimensions as obstacleGrid to store the
10 // number of ways to reach each cell.
11 vector<vector<int>> dp(numberOfRows, vector<int>(numberOfColumns, 0));
12
13 // Initialize the first column of the dp matrix. A cell in the first column can only be reached from
14 // the cell above it, so if there's an obstacle in a cell, all cells below it should be 0 as well.
15 for (int i = 0; i < numberOfRows && obstacleGrid[i][0] == 0; ++i) {
16 dp[i][0] = 1;
17 }
18
19 // Similarly, initialize the first row of the dp matrix. A cell in the first row can only be reached from
20 // the cell to the left of it, so if there's an obstacle in a cell, all cells to the right of it should be 0.
21 for (int j = 0; j < numberOfColumns && obstacleGrid[0][j] == 0; ++j) {
22 dp[0][j] = 1;
23 }
24
25 // Start from cell (1, 1) and fill in the dp matrix until the bottom-right corner of the grid.
26 // The value of dp[i][j] is obtained by adding the values from the cell above (dp[i - 1][j]) and
27 // the cell to the left (dp[i][j - 1]).
28 for (int i = 1; i < numberOfRows; ++i) {
29 for (int j = 1; j < numberOfColumns; ++j) {
30 // If there's no obstacle in the current cell, calculate the number of paths.
31 if (obstacleGrid[i][j] == 0) {
32 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
33 }
34 // If there's an obstacle, the number of paths to the current cell will be 0.
35 }
36 }
37
38 // The bottom-right cell of the dp matrix contains the number of unique paths
39 // from the top-left corner to the bottom-right corner, which we return.
40 return dp[numberOfRows - 1][numberOfColumns - 1];
41 }
42};
43
1// Calculates the number of unique paths on a grid with obstacles.
2// Each path moves only rightward or downward at any point, avoiding obstacles.
3function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
4 // Number of rows and columns in the grid
5 const rowCount = obstacleGrid.length;
6 const colCount = obstacleGrid[0].length;
7
8 // Initializing a 2D array to store the number of ways to reach each cell
9 const dp = Array.from({ length: rowCount }, () => new Array(colCount).fill(0));
10
11 // Filling in the first column, taking obstacles into account
12 for (let row = 0; row < rowCount; row++) {
13 if (obstacleGrid[row][0] === 1) {
14 break; // If there's an obstacle, no path can pass through here
15 }
16 dp[row][0] = 1; // Without obstacles, there's 1 way to get to each cell in the first column
17 }
18
19 // Filling in the first row, taking obstacles into account
20 for (let col = 0; col < colCount; col++) {
21 if (obstacleGrid[0][col] === 1) {
22 break; // If there's an obstacle, no path can pass through here
23 }
24 dp[0][col] = 1; // Without obstacles, there's 1 way to get to each cell in the first row
25 }
26
27 // Calculating paths for the rest of the grid
28 for (let row = 1; row < rowCount; row++) {
29 for (let col = 1; col < colCount; col++) {
30 // If the current cell has an obstacle, skip and continue
31 if (obstacleGrid[row][col] === 1) {
32 continue;
33 }
34
35 // Number of paths to current cell is the sum of paths from the cell above and to the left
36 dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
37 }
38 }
39
40 // Returning the total number of ways to reach the bottom-right corner of the grid
41 return dp[rowCount - 1][colCount - 1];
42}
43
Time and Space Complexity
The time complexity of the provided code is O(m*n)
where m
is the number of rows and n
is the number of columns in the obstacleGrid
. This is because the code contains two nested loops that iterate over each cell in the m x n
grid exactly once, and the operations inside the loop are constant time operations.
The space complexity of the provided code is also O(m*n)
since it uses a 2D list dp
with the same dimensions as the obstacleGrid
to store the number of unique paths to each cell.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.