Unique Paths II medium

Problem Statement

You are given an m x n integer array obstacleGrid where obstacleGrid[i][j] equals 0 if an obstacle exists at the cell (i, j) and 1 otherwise.

You can only move either down or right at any point in time.

You are trying to determine how many different ways there are to reach the bottom-right cell (m-1, n-1) from the top-left cell (0, 0).

Return the number of ways to reach the bottom-right cell in the grid from the top-left cell. If there is an obstacle blocking the path to the bottom-right cell, return 0.

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 and there are two ways to reach the bottom-right corner from the top left corner as shown in the image.

Example 2

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

Steps

1. Initialization: Create a DP table of the same size as the obstacleGrid, initially filled with zeros.
2. Base Case: If the top-left cell obstacleGrid[0][0] contains an obstacle (value 1), there are no paths, so return 0. Otherwise, set dp[0][0] = 1 (one way to reach the starting point).
3. First Row and First Column: Iterate through the first row and first column. If a cell contains an obstacle, the number of paths to reach that cell is 0. Otherwise, the number of paths is equal to the number of paths to reach the cell to its left (or above, depending on whether you're processing the row or the column).
4. Rest of the Grid: Iterate through the rest of the grid. If a cell contains an obstacle, the number of paths to reach that cell is 0. Otherwise, the number of paths is the sum of the number of paths to reach the cell from its left and from the cell above it.
5. Return Value: The value at dp[m-1][n-1] represents the total number of paths to reach the bottom-right cell.

Explanation

This problem is a variation of the classic "Unique Paths" problem, with the addition of obstacles. We use dynamic programming to solve this efficiently. The DP table dp[i][j] stores the number of ways to reach cell (i, j). The value at each cell depends on the values of the cells above and to the left. If a cell is blocked by an obstacle, it cannot be reached, hence the value of 0. The base case handles the starting point and the first row/column, while the iterative process calculates the number of paths for the rest of the grid.

Code

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // Create DP table
        int[][] dp = new int[m][n];

        // Base case: Check for obstacle at starting point
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        dp[0][0] = 1;

        // Fill first row
        for (int i = 1; i < n; i++) {
            if (obstacleGrid[0][i] == 0) {
                dp[0][i] = dp[0][i - 1];
            }
        }

        // Fill first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = dp[i - 1][0];
            }
        }

        // Fill the rest of the DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the grid once to populate the DP table.
• Space Complexity: O(m*n), as we use a DP table of the same size as the input grid. Note that we can optimize space to O(n) by using a 1D array if we process the grid row by row.