Unique Paths II

Medium20–25 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonMicrosoftBloomberg

This is the same right/down path-counting question as Unique Paths, except some cells in the grid are now blocked and can't be stepped on at all. Given a grid marked with open (0) and blocked (1) cells, count how many distinct right/down paths get from the top-left corner to the bottom-right corner without ever passing through a blocked cell. The reasoning carries over directly from the unobstructed version: the number of ways to reach an open cell is the ways that could arrive from above plus the ways that could arrive from the left. The only change is that a blocked cell contributes exactly 0 ways to reach it, no matter what arrives from either direction, since stepping onto it isn't allowed at all — and that 0 then correctly propagates forward, since no path can continue from a cell it was never able to enter. Sweeping the grid the same way, row by row, automatically accounts for every detour the obstacles force.

Test Case 1:

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

Output:3

Explanation:The blocked cell at row 0, column 1 rules out one whole family of paths, leaving 3 valid right/down routes.

Test Case 2:

Input:grid = [[0,0],[0,0]]

Output:2

Explanation:With no blocked cells, a 2×2 grid has 2 paths, matching plain Unique Paths.

Test Case 3:

Input:grid = [[1,0]]

Output:0

Explanation:The starting cell itself is blocked, so no path can even begin.

Constraints

◆1 ≤ grid.length, grid[0].length ≤ 50
◆grid[i][j] is 0 (open) or 1 (blocked)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

This is the same right/down search as plain Unique Paths, with one extra rule: stepping onto a blocked cell ends that path immediately and contributes nothing, exactly like stepping off the grid entirely. From any open cell, the number of ways to reach the bottom-right corner is the ways from moving down plus the ways from moving right — checked before either move is taken, since a blocked neighbor simply isn't a valid move to explore. Reaching the bottom-right corner while it's open counts as one complete path.

TimeO(2^(m+n))

SpaceO(m + n)

Java

Try it out

class Solution {
    private int[][] grid;
    private int m;
    private int n;

    public int uniquePathsII(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        return solve(0, 0);
    }

    private int solve(int i, int j) {
        if (i >= m || j >= n || grid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        return solve(i + 1, j) + solve(i, j + 1);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Sweep the same row-by-row count used for plain Unique Paths, with one change: whenever the current cell is blocked, its count is forced to 0 regardless of what arrived from above or the left, since no path can pass through it. An open cell still adds whatever count is already sitting there (arriving from above) to the count just computed at the cell to its left (arriving from the left) — except in the very first column, where there's no left-neighbor to add. The starting cell is seeded with a single way to reach it, provided it isn't itself blocked, and the entry at the last column after every row has been swept holds the total.

TimeO(m × n)

SpaceO(n)