LeetCode 63 – Unique Paths II | Love Me Some Coding

Unique Paths with obstacles. The recurrence does not change; one guard is added in front of it. That makes this problem a good test of whether you understood the first one or memorised it — and it has an initialisation trap that catches people who did both.

The problem

Same robot, same rules — right and down only — but some cells contain obstacles, marked 1. Count the paths from top-left to bottom-right that avoid them.

[[0,0,0],          -> 2      the middle cell is blocked, so the two
 [0,1,0],                     paths go around it, one each side
 [0,0,0]]

[[0,1],            -> 1
 [0,0]]

[[1]]              -> 0      the start itself is blocked
[[0,0],[1,1],[0,0]] -> 0     an entire row is a wall

One guard, in front of the same recurrence

An obstacle is not a cell with fewer paths through it. It is a cell with zero paths through it, permanently, regardless of what leads into it. So:

paths[r][c] = 0                                if grid[r][c] is an obstacle
            = paths[r-1][c] + paths[r][c-1]    otherwise

That is the entire difference. Everything downstream falls out on its own — a blocked cell contributes 0 to its neighbours, so the wall propagates without any extra code. This is the part worth pointing at: you do not need to detect that a region is unreachable, because zero is already the right answer and it spreads by itself.

The initialisation trap

In Unique Paths the first row and first column were filled with 1s unconditionally. Here they cannot be, and getting this wrong produces answers that are too large on exactly the inputs a quick mental test does not cover.

first row  [0, 0, 1, 0, 0]
  naive    [1, 1, 1, 1, 1]      wrong -- you cannot walk through the wall
  correct  [1, 1, 0, 0, 0]      everything past the obstacle is unreachable

In the top row the robot can only move right, so one obstacle cuts off every cell after it. Same for the left column going down. The clean way to say that in code is that a first-row cell is 1 only if it is not blocked and the cell before it was reachable — which is just the general recurrence with the missing neighbour treated as 0.

That is why the implementation below does not special-case the edges at all. Seed row[0] = 1 for the start, then let the same loop handle everything, reading a non-existent left neighbour as 0.

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int n = grid[0].length;
        int[] row = new int[n];
        row[0] = 1;                     // one way to be at the start...

        for (int[] gridRow : grid) {
            for (int c = 0; c < n; c++) {
                if (gridRow[c] == 1) {
                    row[c] = 0;         // ...unless something is standing on it
                } else if (c > 0) {
                    row[c] += row[c - 1];
                }
                // c == 0 and not blocked: row[0] carries down unchanged, which is
                // exactly right -- the only way into the left column is from above.
            }
        }

        return row[n - 1];
    }
}

The loop starts at c = 0 and includes the very first row, which is what makes the edges free. On row 0 every row[c] is still 0 except row[0], so the sweep naturally produces 1, 1, 0, 0, 0 for the blocked example above. A blocked start sets row[0] = 0 on the first iteration and the whole grid stays 0.

Watch the overflow question. LeetCode guarantees the answer fits in a 32-bit int for this problem's constraints, but say that you checked rather than not noticing — with a 100 × 100 empty grid the unconstrained count is astronomically larger than Integer.MAX_VALUE.

Python

class Solution:
    def uniquePathsWithObstacles(self, grid: list[list[int]]) -> int:
        n = len(grid[0])
        row = [0] * n
        row[0] = 1

        for grid_row in grid:
            for c in range(n):
                if grid_row[c] == 1:
                    row[c] = 0
                elif c > 0:
                    row[c] += row[c - 1]

        return row[-1]

Python has no overflow to worry about, which is a real difference worth naming rather than glossing over: the same code that is safe here would need a long or a modulus in Java if the constraints were loosened.

Complexity

	Time	Space
Rolling row	`O(m · n)`	`O(n)`

Every cell is read once. There is no early exit worth adding — a fully blocked row makes the rest of the sweep produce zeros anyway, and detecting it costs a branch on every cell to save work on inputs that barely occur.

The in-place variant, and why to ask first

You can write the counts into grid itself and use O(1) extra space. It is a legitimate answer and interviewers sometimes fish for it.

It also destroys the caller's input, which matters more often than the space does. Ask whether mutating the argument is acceptable before doing it — the question itself scores better than either answer, because it shows you know the trade rather than making it silently.

What the interviewer is checking

That the obstacle rule is zero paths, not a special case to route around.
The first row and first column — an obstacle cuts off everything after it.
That a blocked start or a blocked finish returns 0.
That zeros propagate on their own, with no unreachable-region detection.
Whether you raise integer overflow rather than being told about it.
That you ask before mutating the input grid.