Unique Paths II: grid paths with obstacles

• Grid DP – dp[i][j] counts the distinct paths from top-left to cell (i, j) moving only right or down.
• Obstacle rule – any cell marked as an obstacle has dp[i][j] = 0, eliminating all paths through it.
• Free cell transition – dp[i][j] = dp[i-1][j] + dp[i][j-1] for non-obstacle cells.
• Edge initialisation – the first row and first column accumulate 1s until the first obstacle, then everything beyond is 0.
• Complexity – O(m * n) time, reducible to O(n) space with a rolling row.

What is the Unique Paths II problem?

You have an m-by-n grid where each cell is either free (0) or blocked (1). A robot starts at the top-left corner and can only move right or down. The goal is to count the number of distinct paths from the top-left to the bottom-right that avoid all blocked cells.

In banking, this is like routing a document through a grid of approval offices where some are temporarily closed. Each valid path represents a feasible approval chain.

How does the DP recurrence work?

For a free cell, the number of paths to reach it is the sum of paths from directly above and directly to the left, because those are the only two directions the robot can arrive from. For an obstacle cell, the count is zero because the robot cannot enter it.

package com.bank.service;

public class DocumentRoutingService {

    public static int countRoutes(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        // If start or end is blocked, no path exists
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return 0;

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        // First column: accumulate until first obstacle
        for (int i = 1; i < m; i++) {
            dp[i][0] = (grid[i][0] == 0 && dp[i - 1][0] == 1) ? 1 : 0;
        }

        // First row: accumulate until first obstacle
        for (int j = 1; j < n; j++) {
            dp[0][j] = (grid[0][j] == 0 && dp[0][j - 1] == 1) ? 1 : 0;
        }

        // Fill interior cells
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (grid[i][j] == 1) ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        System.out.println("Distinct routes: " + countRoutes(grid));
    }
}

Distinct routes: 2

How is this different from Unique Paths I (no obstacles)?

| Aspect | Unique Paths I | Unique Paths II |
|---|---|---|
| Grid content | All cells free | Some cells blocked |
| First row/column | All 1s | 1s until first obstacle, then 0s |
| Transition | dp[i][j] = above + left | Same, but obstacle cells forced to 0 |
| Formula shortcut | C(m+n-2, m-1) combinatorics | No closed-form due to obstacles |

The obstacle-free version has a direct combinatorial formula: choose m-1 down-moves out of m+n-2 total moves. Obstacles break this formula because they remove specific paths, so the DP approach is necessary.

// Unique Paths I: combinatorial solution (no obstacles)
public static long uniquePathsCombinatorial(int m, int n) {
    long result = 1;
    for (int i = 1; i < m; i++) {
        result = result * (n - 1 + i) / i;
    }
    return result;
}

How do you handle edge initialisation?

The first row can only be reached from the left, and the first column can only be reached from above. Along these edges, once an obstacle appears, every cell beyond it is unreachable because there is only one direction of travel.

// First row: once we hit an obstacle, everything after is 0
// grid[0] = [0, 0, 1, 0, 0]
// dp[0]   = [1, 1, 0, 0, 0]  <-- 0s propagate after obstacle

// First column: same logic vertically
// grid[i][0] = [0, 0, 1, 0]
// dp[i][0]   = [1, 1, 0, 0]

How do you optimise space to O(n)?

Use a single rolling row. Process the grid row by row, updating each cell in place. An obstacle cell is set to zero. A free cell adds the value to its left (already updated for the current row) and the value in the same column from the previous row (still in the array from the previous iteration).

public static int countRoutesOptimised(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return 0;

    int[] dp = new int[n];
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

What are the edge cases?

• Start is blocked – return 0, the robot cannot even begin.
• End is blocked – return 0, the destination is unreachable.
• 1x1 grid with no obstacle – return 1, the robot is already there.
• Entire first row blocked at index 0 – return 0.
• No obstacles at all – the answer is the same as Unique Paths I.

// Edge case: 1x1 grid
int[][] single = {{0}};
System.out.println(countRoutes(single)); // 1

// Edge case: start blocked
int[][] blocked = {{1}};
System.out.println(countRoutes(blocked)); // 0

What are common mistakes?

The most common mistake is not zeroing the first row and column cells after an obstacle.

// WRONG: setting first row all to 1
for (int j = 0; j < n; j++) dp[0][j] = 1; // ignores obstacles

// CORRECT: stop at first obstacle
for (int j = 1; j < n; j++) {
    dp[0][j] = (grid[0][j] == 0 && dp[0][j - 1] == 1) ? 1 : 0;
}

Another mistake is forgetting to check if the destination itself is blocked before running the DP.

What is the time and space complexity?

Time is O(m * n) because every cell is visited once. Space is O(m * n) for the full DP table, or O(n) with the rolling row optimisation. For a banking document routing grid of 100 x 100, this runs in microseconds.

What should a senior engineer know?

A senior engineer should know that the rolling-row optimisation works because each row depends only on the current row (left neighbour) and the previous row (above neighbour). They should also know that this problem cannot be solved with the combinatorial formula because obstacles create irregular forbidden zones.

For very large grids with sparse obstacles, the path count can overflow an int. Using long or BigInteger is necessary for grids where the path count exceeds 2^31 - 1.