Unique Paths II medium

Problem Statement

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 empty space is marked as 1 and 0 respectively in the grid.

For example,

obstacleGrid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

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 which prevents 2 paths from being formed.

Example 2:

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

Steps to Solve

1. Handle Base Cases: If the starting cell (top-left) has an obstacle (obstacleGrid[0][0] == 1), there are no paths. If the grid is empty or only contains one element, handle those cases separately.

2. Initialization: Create a DP table (2D vector) of the same size as the grid to store the number of paths to reach each cell. Initialize the first row and column of the DP table. A cell can only be reached if there's no obstacle and the cell to its left or above is reachable.

3. Iteration: Iterate through the DP table. For each cell (i, j), if there's no obstacle at (i, j):

   • The number of paths to reach (i, j) is the sum of the paths to reach (i-1, j) and (i, j-1). -Otherwise, set the number of paths to 0 (obstacle blocks path).

4. Return Result: The bottom-right cell of the DP table contains the total number of unique paths.

Explanation

The dynamic programming approach is used because the problem exhibits overlapping subproblems. The number of paths to reach a given cell depends on the number of paths to reach the cells above and to its left. By storing these intermediate results in the DP table, we avoid redundant calculations. The iterative approach is more efficient than recursion in this case because it avoids the overhead of recursive function calls.

Code (C++)

#include <vector>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();

    // Handle base cases
    if (obstacleGrid[0][0] == 1) return 0;
    if (m == 1 && n == 1 && obstacleGrid[0][0] == 0) return 1;


    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    dp[0][0] = 1; // One path to reach the starting cell


    // Initialize first row and column
    for (int i = 1; i < m; ++i) {
        if (obstacleGrid[i][0] == 0)
            dp[i][0] = dp[i - 1][0];
    }
    for (int j = 1; j < n; ++j) {
        if (obstacleGrid[0][j] == 0)
            dp[0][j] = dp[0][j - 1];
    }


    // Fill 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 DP table once.
• Space Complexity: O(m*n), the space used by the DP table. We could optimize this to O(min(m,n)) by using a 1D array, but the 2D array improves readability.