Room 04 · The Grind — 2-D Dynamic Programming

Unique Paths II

MEDIUM✓ CHIP-TIMEDLC #63 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Same right/down grid walk as before, but some cells are boulders that block the route entirely. Count the paths from the top-left corner to the bottom-right that never step on one.

The same right/down grid walk returns, except now some cells are marked as obstacles that block the route entirely — a route can never step onto one of those cells.

The runner still starts in the top-left corner and must reach the bottom-right corner using only right and down moves, and the count needed is how many distinct obstacle-free routes exist between those two corners.

If the starting cell or the ending cell itself is blocked, no route can exist at all, and the answer collapses to zero.

the grid marks obstacles distinctly from open cells
the start or end cell can itself be an obstacle, giving zero routes
movement is limited to a single step right or a single step down
grid sizes stay small enough for an O(m·n) table

EX 01

obstacleGrid = [[0]]

→ 1

single open cell

EX 02

obstacleGrid = [[1]]

→ 0

single cell, blocked

EX 03

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

→ 2

a two-wide wall forces a detour

The hintstake only what you need

HINT 1 THE NUDGE

The recursion is identical to the open grid — except a blocked cell contributes zero routes instead of one. Where does that zero need to propagate?

HINT 2 THE STRUCTURE

A blocked cell has no ways to be reached and nothing to pass forward — both directions collapse to zero, including if the blocker sits on the starting cell itself.

HINT 3 ONE STEP FROM THE ANSWER

Reuse the rolling-row DP: ways[c] += ways[c-1] normally, but slam ways[c] to 0 the instant an obstacle occupies that cell, before it can contribute to its neighbour.

Coach's boardthe pattern, step by step

THE DETOUR COUNTPATTERN · GRID DP, OBSTACLES ZERO OUT3×4 grid · obstacles at (1,1) and (1,2)

STEP 1

Seed the entrance with one way to stand there, doing nothing.

STEP 1 / 6 · ← → WORK TOO

The splitstwo paces, two languages

grind/unique-paths-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        row = [0] * n
        row[0] = 1
        for r in range(m):
            for c in range(n):
                if obstacleGrid[r][c] == 1:
                    row[c] = 0
                elif c > 0:
                    row[c] += row[c - 1]
        return row[-1]

TIME O(M·N)SPACE O(N)PYTHON · RACE PACE · 12 LN

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        def paths(r, c):
            if obstacleGrid[r][c] == 1:
                return 0
            if r == m - 1 and c == n - 1:
                return 1
            total = 0
            if r + 1 < m:
                total += paths(r + 1, c)
            if c + 1 < n:
                total += paths(r, c + 1)
            return total

        return paths(0, 0)

TIME O(2^(M+N))SPACE O(M+N)PYTHON · TRAINING PACE · 17 LN

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] row = new int[n];
        row[0] = 1;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (obstacleGrid[r][c] == 1) {
                    row[c] = 0;
                } else if (c > 0) {
                    row[c] += row[c - 1];
                }
            }
        }
        return row[n - 1];
    }
}

TIME O(M·N)SPACE O(N)JAVA · RACE PACE · 17 LN

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

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        grid = obstacleGrid;
        m = grid.length;
        n = grid[0].length;
        return paths(0, 0);
    }

    private int paths(int r, int c) {
        if (grid[r][c] == 1) {
            return 0;
        }
        if (r == m - 1 && c == n - 1) {
            return 1;
        }
        int total = 0;
        if (r + 1 < m) {
            total += paths(r + 1, c);
        }
        if (c + 1 < n) {
            total += paths(r, c + 1);
        }
        return total;
    }
}

TIME O(2^(M+N))SPACE O(M+N)JAVA · TRAINING PACE · 28 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED