☕ DSA Java Articles

Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Unique paths II

Medium TUF ID 300 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A robot starts at the top-left cell of an m × n grid and wants to reach the bottom-right cell, moving only right or down. Some cells are blocked: grid[i][j] == 1 marks an obstacle and 0 a free cell. A path may not pass through a blocked cell. Count the distinct paths.

This follows LeetCode 63. Some versions (for example Coding Ninjas “Maze Obstacles”) mark blocked cells with -1 instead; only the obstacle test changes.

Constraints: 1 ≤ m, n ≤ 100, and the answer fits in an int. If the start or the target is blocked, the answer is 0.

Example 1

grid = [[0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]]
answer = 2          // around the centre obstacle: right-right-down-down or down-down-right-right

Example 2

grid = [[0, 1],
        [0, 0]]
answer = 1          // down, then right

Why the formula from Unique Paths fails

Without obstacles every arrangement of m - 1 downs and n - 1 rights is a valid path, so the answer is a binomial coefficient. With obstacles, some of those arrangements pass through a blocked cell, and how many do depends on where the obstacles are. There is no clean formula, but the DP needs only one extra line: a blocked cell has zero paths through it.

Approach 1: Recursion

Intuition. Let f(i, j) be the number of obstacle-free paths from (0, 0) to (i, j). As in the obstacle-free problem, the last move into (i, j) came from above or from the left, and those two groups of paths do not overlap. The only change: if (i, j) is blocked, no path ends there, so f(i, j) = 0 regardless of its neighbours.

f(i, j) = 0                              if i < 0, j < 0, or grid[i][j] == 1
f(0, 0) = 1                              (when the start is free)
f(i, j) = f(i - 1, j) + f(i, j - 1)      otherwise

The order of the checks matters. The bounds test must come before grid[i][j] is read, and the obstacle test must come before the start test, so that a blocked start correctly returns 0.

Algorithm.

  1. If i < 0, j < 0, or the cell is blocked, return 0.
  2. If (i, j) == (0, 0), return 1.
  3. Return f(i - 1, j) + f(i, j - 1).
static int recursive(int[][] grid) {
    return paths(grid.length - 1, grid[0].length - 1, grid);
}

static int paths(int i, int j, int[][] grid) {
    if (i < 0 || j < 0 || grid[i][j] == 1) return 0;       // off the grid or blocked: no path goes through here
    if (i == 0 && j == 0) return 1;
    return paths(i - 1, j, grid) + paths(i, j - 1, grid);
}

Complexity. Time O(2^(m+n)) in the worst case (no obstacles). Space O(m + n) for the recursion stack.

Approach 2: Memoization

Intuition. The state is a cell, so there are m · n states, and the plain recursion revisits them many times. Cache them in dp[i][j]. Obstacles and out-of-range cells are answered by the base case before the cache is touched, so they never need a table entry.

Algorithm.

  1. Create dp[m][n] filled with -1.
  2. Apply the base cases, then return dp[i][j] if filled; otherwise compute, store and return.
static int memoization(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(m - 1, n - 1, grid, dp);
}

static int memo(int i, int j, int[][] grid, int[][] dp) {
    if (i < 0 || j < 0 || grid[i][j] == 1) return 0;
    if (i == 0 && j == 0) return 1;
    if (dp[i][j] != -1) return dp[i][j];
    return dp[i][j] = memo(i - 1, j, grid, dp) + memo(i, j - 1, grid, dp);
}

Complexity. Time O(m · n), space O(m · n) plus O(m + n) stack.

Approach 3: Tabulation

Intuition. Fill the table row by row, left to right, so the cell above and the cell to the left are always ready. A blocked cell gets 0, which automatically cuts off every path that would go through it: any cell after it can only add 0 from that direction.

Algorithm.

  1. For each cell in row-major order:
    • if blocked, dp[i][j] = 0;
    • else if it is the start, dp[i][j] = 1;
    • else dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0).
  2. Return dp[m - 1][n - 1].
static int tabulation(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) { dp[i][j] = 0; continue; }  // blocked cells hold 0 paths
            if (i == 0 && j == 0) { dp[i][j] = 1; continue; }
            int up = i > 0 ? dp[i - 1][j] : 0;
            int left = j > 0 ? dp[i][j - 1] : 0;
            dp[i][j] = up + left;
        }
    }
    return dp[m - 1][n - 1];
}

Dry run on Example 1:

  j=0 j=1 j=2
i=0 1 1 1
i=1 1 0 (blocked) 1
i=2 1 1 2

dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0, and dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2.

Complexity. Time O(m · n), space O(m · n).

Approach 4: Space optimized

Intuition. Exactly as in the obstacle-free version, a single array row is enough: before row[j] is updated it holds the value from the row above, and row[j - 1] already holds this row’s value to the left. A blocked cell simply resets row[j] to 0.

Start with row[0] = 1, meaning one way to “arrive” at the start. If the start is blocked, the very first cell visited sets it back to 0, and everything after stays 0.

Algorithm.

  1. row = [1, 0, ..., 0].
  2. For each grid row, for j from 0 to n - 1: if the cell is blocked, row[j] = 0; otherwise, if j > 0, row[j] += row[j - 1].
  3. Return row[n - 1].

Column 0 has no left neighbour, so a free cell there keeps the value from above. That is right: the only way into column 0 is from above.

static int spaceOptimized(int[][] grid) {
    int n = grid[0].length;
    int[] row = new int[n];
    row[0] = 1;                                             // one way to "arrive" at the start, cleared below if it is blocked
    for (int[] cells : grid) {
        for (int j = 0; j < n; j++) {
            if (cells[j] == 1) row[j] = 0;
            else if (j > 0) row[j] += row[j - 1];           // from above (old row[j]) + from the left
        }
    }
    return row[n - 1];
}

Complexity. Time O(m · n), space O(n).

Edge cases and pitfalls