What is the brute force approach and complexity for Unique Paths II?

Count the paths into a cell by adding the two cells that feed it; an obstacle counts as 0 with time complexity O(2^(M + N)) and space complexity O(M + N).

What is the optimal approach and complexity for Unique Paths II?

One row of counts: an obstacle sets row[c] = 0, and the flow from the left carries on from there with optimal time complexity O(M · N) and space complexity O(N).

How do you identify the pattern for Unique Paths II?

Look for key signals in the prompt: "some cells are obstacles" indicates An obstacle has 0 paths. It changes the starting values of the rows and columns, and it changes the sums for the cells it blocks.; "move only down or right" indicates The same two feeders as Unique Paths, so the table still reads only the cell above and the cell to the left.; "the number of paths" indicates The goal is still a count, so every free cell is still a sum of its feeders..

Unique Paths II

Medium·LeetCode #63 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

The same robot starts at the top-left cell of a grid and wants the bottom-right cell. It still moves only down or right. This time some cells hold an obstacle (value 1), and the robot cannot step on them. A free cell has value 0.

Return how many paths avoid every obstacle. If the start or the end cell is an obstacle, the answer is 0.

Input

obstacleGrid, an m × n grid. 0 is a free cell and 1 is an obstacle.

Output

The number of paths from the top-left cell to the bottom-right cell that never touch an obstacle.

Example 1

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

Output: 2

The obstacle in the middle blocks every path through it. The two paths left are Right → Right → Down → Down and Down → Down → Right → Right.

Example 2

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

Output: 1

Going right first runs into the obstacle, so the only path is Down → Right.

Constraints

• 1 ≤ m, n ≤ 100
• Each cell is 0 or 1.
• The tests are chosen so that the answer is at most 2 × 10^9.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“some cells are obstacles”

→ An obstacle has 0 paths. It changes the starting values of the rows and columns, and it changes the sums for the cells it blocks.

“move only down or right”

→ The same two feeders as Unique Paths, so the table still reads only the cell above and the cell to the left.

“the number of paths”

→ The goal is still a count, so every free cell is still a sum of its feeders.

Approach Complexity Ladder

Brute Force — recurse back from the corner, skipping obstaclesO(2^(M + N))O(M + N)

Count the paths into a cell by adding the two cells that feed it; an obstacle counts as 0

Better — a table of counts, with obstacles set to 0O(M · N)O(M · N)

dp[r][c] = 0 on an obstacle, otherwise dp above + dp left, with each cell worked out once

Optimal — one row, obstacles reset to 0O(M · N)O(N)

One row of counts: an obstacle sets row[c] = 0, and the flow from the left carries on from there

Brute Force Intuition

Let ways(r, c) be the number of obstacle-free paths from the top-left to (r, c). An obstacle has 0 paths. Any other cell is the cell above plus the cell to its left, and the start has 1 path. Start the recursion at the bottom-right corner.

Recognition rule for this sub-pattern:

dp[r][c] = dp[r−1][c] + dp[r][c−1] (ways) or min(…) + cost (cost).

Remember this · DP — Grid

Trigger

Move only right/down, count paths, minimum path cost, largest square of 1s.

Think

To reach cell (r, c), which cells could I have come from?

Key question

What does dp[r][c] mean, and what are the first row/column?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture