TRT
Sign in
mediumAdvancedLeetCode#grid DP#obstacles

Unique paths II

Count right-and-down paths through a grid with obstacles, setting blocked cells to zero.

The Runtime Theory Team1 min read
Taught inGrids and stringsPro — members onlyTwo-dimensional DP fills a table whose cells depend on their neighbors above and to the left. On grids it counts or optimizes paths; on two strings, a cell compares two prefixes, which is how diff tools, spell checkers and DNA alignment work.
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

ingrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]

out2

ingrid = [[0, 1], [0, 0]]

out1

ingrid = [[1]]

out0

Same as Unique paths, but cells marked 1 are obstacles that paths can't enter.

Before you code

A blocked cell has zero paths, and that zero propagates: nothing passes through it.

Hints

  1. If the start is blocked, the answer is 0.
  2. Blocked cells get 0; others get above + left.
  3. Watch the first row and column: once blocked, every cell after it in that row or column has 0.

Production & complexity notes

When solving Unique paths II on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Grids and strings to reinforce the underlying pattern.

What it practices

Grid DP with constraints, from Grids and strings.

More practice in this track

hard · dsaDesign a skip listmedium · dsaDesign a bounded blocking queueeasy · dsaRange sum query: immutable

Not started

Sign in to save your learning progress.

Sign in to save