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:

1. Start by initializing a 2D array dp (same dimensions as grid) to store the number of ways to reach each cell.
2. Set the value of dp[i][0] (first column) and dp[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.
3. Loop through the grid starting from cell dp[1][1] and move rightward and downward.
4. For every cell, check if it is not an obstacle. If it isn't, set dp[i][j] to the sum of dp[i - 1][j] (the number of ways to reach from above) and dp[i][j - 1] (the number of ways to reach from the left).
5. If you encounter an obstacle, set the number of ways to 0 because the robot can't pass through obstacles.
6. Continue this process until you reach the bottom-right corner of the grid.
7. 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.

1. Data Structure: A 2-dimensional list dp of size m x n (where m and n are the dimensions of the input grid) is initialized with zeros. This dp list is used to store the number of unique paths to reach each cell (i, j) from the start (0, 0).

2. 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.

3. 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.

4. 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.

Example 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].

1. Data Structure Initialization: Initialize the dp array with zeros.

   1dp = [
   2    [0, 0, 0],
   3    [0, 0, 0],
   4    [0, 0, 0]
   5]

2. 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 leave dp[1][1] as 0.

3. 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 in dp[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 in dp[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 us dp[2][2] = 2.

   Final dp array:

   1dp = [
   2    [1, 1, 1],
   3    [1, 0, 1],
   4    [1, 1, 2]
   5]

4. 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

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.