~/DHRUVUpskilling
← board/DSA/Dynamic Programming/dsa-dynamic-programming-09
Solved·02 Oct

Unique Paths II

DifficultyMedium
PatternDynamic Programming
TrackDSA
tl;dr

Avoid going through obstacle and return total number of ways to reach destination

full write-up

Unique Paths II (With Obstacles)

Problem Statement

You are given an m x n integer grid, grid. A robot starts at the top-left corner (grid[0][0]), and wants to reach the bottom-right corner (grid[m-1][n-1]). The robot can only move down or right at any point.

Obstacles and open spaces are marked as 1 and 0 respectively in the grid. The robot's path cannot pass through any square marked as an obstacle.

Return the number of unique paths the robot can take to reach the bottom-right corner.

Note: The test cases are designed so that the answer will always be less than or equal to 2 × 10⁹.

Examples

Example 1

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

Output: 2

Explanation: There is one obstacle in the middle of this 3x3 grid. 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

Solution

Brute Force

We use recursion, working backward from the bottom-right corner toward the top-left corner. At each cell, the number of ways to reach it is the sum of the ways to reach the cell above it and the cell to its left.

  • If a position is out of bounds, or lands on an obstacle, there are 0 ways to reach it from there.
  • The starting cell (0, 0) always has exactly 1 way to "reach" it (since that's where the robot begins).
var uniquePathsWithObstacles = function (obstacleGrid) {

    function recurr(i, j) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
            return 0;
        }

        if (i == 0 && j == 0) {
            return 1;
        }

        let up = recurr(i - 1, j);
        let right = recurr(i, j - 1);

        return right + up;
    }

    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;

    return recurr(m - 1, n - 1);
};

Note: The variable named right here actually represents the result of moving to (i, j - 1), which is the cell to the left, not the right. This doesn't affect correctness — the final sum is the same either way — but the naming could be a little confusing if you're reading through the logic carefully.

Memoization (Top-Down)

We use the same recursive approach, but store each cell's result in a dp grid the first time we calculate it, so we don't repeat the same calculations.

var uniquePathsWithObstacles = function (obstacleGrid) {

    function recurr(i, j, dp) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
            return 0;
        }

        if (i == 0 && j == 0) {
            return 1;
        }

        if (dp[i][j] !== 0) {
            return dp[i][j];
        }
        let up = recurr(i - 1, j, dp);
        let right = recurr(i, j - 1, dp);
        dp[i][j] = right + up;
        return dp[i][j];
    }

    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;

    let dp = Array.from({ length: m }, () => Array(n).fill(0));

    dp[0][0] = 1;

    return recurr(m - 1, n - 1, dp);
};

Note: Since dp is filled with 0 by default, this code uses dp[i][j] !== 0 to check whether a cell has already been calculated. This works correctly, but it means that any cell whose genuine answer is 0 paths (for example, a cell that's fully blocked off by obstacles) will never get "cached" — it will simply be recalculated as 0 again each time it's visited. This doesn't cause incorrect results, but it's a small inefficiency worth knowing about.

Tabulation (Bottom-Up)

Instead of recursing from the end, we build the answer forward, starting from the top-left corner and working toward the bottom-right.

  • If a cell has an obstacle, it has 0 ways to be reached, and we skip it.
  • The starting cell has exactly 1 way to be reached.
  • Every other cell's value is the sum of the cell above it and the cell to its left (treating out-of-bounds neighbors as 0).
var uniquePathsWithObstacles = function (obstacleGrid) {

    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;

    let dp = Array.from({ length: m }, () => Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 0 && j == 0) {
                dp[0][0] = 1;
                continue;
            }

            let up = 0;
            let left = 0;

            if (i > 0) {
                up = dp[i - 1][j];
            }

            if (j > 0) {
                left = dp[i][j - 1];
            }
            dp[i][j] = left + up;
        }
    }

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