63. Unique Paths II

Description

You are given a m x n grid filled with non-negative numbers, where some cells may contain obstacles (represented by 1s). Find the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time. A path cannot pass through a cell with an obstacle.

Intuition

The problem can be visualized as navigating a grid where some cells are blocked. To find the number of unique paths to each cell, we need to consider whether the cell is reachable from its possible predecessors (top or left). This suggests a dynamic programming approach where we build up the solution from the smallest subproblems.

Approach

1. Initialization: - Define a 2D list memo to store the number of unique paths to each cell, initialized to -1. - Start from the top-left corner of the grid and recursively compute the number of unique paths to each cell.
2. Recursive Function: - Base Cases: - If the cell indices are out of bounds or the cell contains an obstacle, return 0. - If the cell is the bottom-right corner, return 1 as it represents a valid path. - Memoization: - If the number of unique paths for a cell is already computed (i.e., memo[i][j] != -1), return the stored value. - Recursive Calculation: - Compute the number of unique paths for the cell directly below and to the right. - Update the cell's value in memo with the sum of the unique paths from the top and left cells.
3. Result: - The result for the top-left corner of the grid will be the number of unique paths from the top-left to bottom-right.

Complexity

Time Complexity:

O(m * n), where m is the number of rows and n is the number of columns in the grid. Each cell is computed only once and stored.

Space Complexity:

O(m * n) for the memoization table memo, plus the recursion stack space which can be up to O(m + n) in the worst case.

Code

C++

class Solution {
public:
    int uniquePathsWithObstacles(vector>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector> memo(m, vector(n, -1));
        return dfs(obstacleGrid, 0, 0, memo);
    }
private:
    int dfs(vector>& obstacleGrid, int i, int j, vector>& memo) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        if (i >= m || j >= n || obstacleGrid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        
        memo[i][j] = dfs(obstacleGrid, i + 1, j, memo) + dfs(obstacleGrid, i, j + 1, memo);
        
        return memo[i][j];
    }
};

Python

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        memo = [[-1 for _ in range(n)] for _ in range(m)]
        return self.dfs(obstacleGrid, 0, 0, memo)
    def dfs(self, obstacleGrid: List[List[int]], i: int, j: int, memo: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if i >= m or j >= n or obstacleGrid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        if memo[i][j] != -1:
            return memo[i][j]
        memo[i][j] = self.dfs(obstacleGrid, i + 1, j, memo) + self.dfs(obstacleGrid, i, j + 1, memo)
        return memo[i][j]

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] memo = new int[m][n];
        // Initialize the memoization array with -1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }
        }
        return dfs(obstacleGrid, 0, 0, memo);
    }
    private int dfs(int[][] obstacleGrid, int i, int j, int[][] memo) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (i >= m || j >= n || obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (i == m - 1 && j == n - 1) {
            return 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        memo[i][j] = dfs(obstacleGrid, i + 1, j, memo) + dfs(obstacleGrid, i, j + 1, memo);
        return memo[i][j];
    }
}

JavaScript

var uniquePathsWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    let memo = Array.from({ length: m }, () => Array(n).fill(-1));

    function dfs(i, j) {
        if (i >= m || j >= n || obstacleGrid[i][j] === 1) return 0;
        if (i === m - 1 && j === n - 1) return 1;
        if (memo[i][j] !== -1) return memo[i][j];

        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);

        return memo[i][j];
    }

    return dfs(0, 0);
};