LeetCode 63. Unique Paths II

Question

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

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 above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

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

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Source: https://leetcode.com/problems/unique-paths-ii/

Solution

For grids occupied by obstacles, we set their number of unique paths to zero. Note that when initializing the first row and column of the DP array, an obstacle will make itself and all following grids unreachable.

// Time Complexity O(mn), Space Complexity O(mn)
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    // dp[i][j] represents the number of unique paths from (0,0) to (i,j)
    int[][] dp = new int[m][n];
    boolean blocked = false;
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            blocked = true;
        }
        if (blocked) {
            dp[i][0] = 0;
        } else {
            dp[i][0] = 1;
        }
    }
    blocked = false;
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            blocked = true;
        }
        if (blocked) {
            dp[0][j] = 0;
        } else {
            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][j - 1] + dp[i - 1][j];
            }
        }
    }
    return dp[m - 1][n - 1];
}