Unique Paths II

Share

You are given an m x n integer array obstacleGrid. A robot is initially located at the top-left corner and tries to reach the bottom-right corner. The robot can only move either down or right. An obstacle is marked with 1 and empty space with 0. Return the number of unique paths that do not pass through any obstacle.

Example 1
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid. There are two unique paths: Right→Right→Down→Down and Down→Down→Right→Right.
Example 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Solution Approach - DP with Obstacle Check

This is an extension of Unique Paths. The key difference is that any cell marked as an obstacle has 0 paths through it. We modify the DP table to set dp[i][j] = 0 whenever obstacleGrid[i][j] == 1.

  • If the start or end cell is an obstacle, immediately return 0.
  • Initialize first row and first column: set to 1 only until an obstacle is encountered; all subsequent cells in that row/column become 0.
  • For all other cells: if the cell is an obstacle set 0, otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1].
Java
public class UniquePathsII {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int i = 1; i < m; i++)
            dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1][0];
        for (int j = 1; j < n; j++)
            dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j - 1];

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
Complexity Analysis:

Time complexity: O(m * n) to traverse every cell once.
Space complexity: O(m * n) for the DP table; can be reduced to O(n) with a 1D array.