Code Implementation

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid or obstacleGrid[0][0] == 1:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    if i > 0:
                        dp[i][j] += dp[i-1][j]
                    if j > 0:
                        dp[i][j] += dp[i][j-1]
        return dp[m-1][n-1]
      

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1) return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];
                    if (j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};
      

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) return 0;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];
                    if (j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
      

var uniquePathsWithObstacles = function(obstacleGrid) {
    if (!obstacleGrid || obstacleGrid[0][0] === 1) return 0;
    let m = obstacleGrid.length, n = obstacleGrid[0].length;
    let dp = Array.from({length: m}, () => Array(n).fill(0));
    dp[0][0] = 1;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0;
            } else {
                if (i > 0) dp[i][j] += dp[i-1][j];
                if (j > 0) dp[i][j] += dp[i][j-1];
            }
        }
    }
    return dp[m-1][n-1];
};
      

Problem Description

You are given a 2D grid represented by obstacleGrid where each cell contains either a 0 (an empty space) or a 1 (an obstacle). The robot starts at the top-left corner (cell [0][0]) and wants to reach the bottom-right corner (cell [m-1][n-1]). The robot can only move either down or right at any point in time.

Your task is to determine how many unique paths exist from the start to the finish, considering the obstacles. If the starting or ending cell contains an obstacle, there are zero ways to reach the destination.

• You may only move right or down.
• Cells with a 1 are blocked and cannot be entered.
• Each path must stay within the grid and avoid obstacles.
• The grid size can be up to 100x100.

Thought Process

At first glance, the problem seems similar to the classic "Unique Paths" problem, where you count the number of ways to go from the top-left to the bottom-right of a grid. However, the presence of obstacles complicates things, because you cannot pass through cells with a 1.

A brute-force approach would be to try all possible paths recursively, but this quickly becomes infeasible for larger grids due to the exponential number of possibilities. We need to avoid recomputation and efficiently account for obstacles.

The key insight is that the number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell to its left—unless that cell is blocked by an obstacle. This naturally leads to a dynamic programming (DP) approach, where we build up the solution by filling out a DP table row by row.

Solution Approach

We'll use a 2D dynamic programming table dp of the same size as obstacleGrid, where dp[i][j] represents the number of unique paths to cell (i, j).

1. Initialization:
   • If the starting cell obstacleGrid[0][0] is 1, there are zero paths. Otherwise, set dp[0][0] = 1.
2. DP Transition:
   • For each cell (i, j) in the grid:
   • If obstacleGrid[i][j] is 1, set dp[i][j] = 0 (blocked).
   • Otherwise, set dp[i][j] = dp[i-1][j] + dp[i][j-1], using 0 if out of bounds.
3. Edge Cases:
   • Cells in the first row or first column can only be reached from one direction if not blocked.
4. Result:
   • The value at dp[m-1][n-1] gives the total unique paths from start to finish.

This approach ensures that each subproblem is solved only once, and obstacles are handled naturally by setting their corresponding DP cells to zero.

Example Walkthrough

Let's work through an example:

Input: obstacleGrid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
  

• Start by setting dp[0][0] = 1 (since it's not blocked).
• Fill the first row: Since there are no obstacles, dp[0][1] = 1, dp[0][2] = 1.
• Fill the first column: dp[1][0] = 1, dp[2][0] = 1.
• Now, for dp[1][1], there's an obstacle, so dp[1][1] = 0.
• For dp[1][2]: dp[1][1] + dp[0][2] = 0 + 1 = 1.
• For dp[2][1]: dp[1][1] + dp[2][0] = 0 + 1 = 1.
• For dp[2][2]: dp[1][2] + dp[2][1] = 1 + 1 = 2.

The final answer is 2, meaning there are two unique paths from the top-left to the bottom-right, avoiding the obstacle.

Time and Space Complexity

• Brute-force:
  • Time: Exponential, O(2^m+n), as you try every possible path.
  • Space: O(m+n) for the recursion stack.
• Dynamic Programming:
  • Time: O(m*n), since each cell is computed once.
  • Space: O(m*n) for the DP table (can be reduced to O(n) with optimization).

The DP approach is efficient and well-suited for large grids.

Summary

The "Unique Paths II" problem extends the classic grid path-counting challenge by adding obstacles. By using dynamic programming, we efficiently compute the number of unique paths from the start to the finish, handling obstacles by setting their DP values to zero. This approach avoids recomputation and leverages the overlapping subproblems inherent in the grid structure, resulting in a solution that is both elegant and performant.