Log inSign up
mediumLeetCodeNot Started

Unique Paths II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

You are given an m x n integer array obstacleGrid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in obstacleGrid. A path that the robot takes cannot include any square that is an obstacle.

Return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1 · Center Obstacle in 3x3 Grid:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid. There are two paths to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

Example 2 · Corner Obstacle in 2x2 Grid:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Explanation: The top-right cell (0,1) is blocked. Only 1 path exists: Down -> Right.

Constraints:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Grid navigation coordinates (down and right transitions)
  • Fundamental Dynamic Programming concepts (optimal substructure, overlapping subproblems)
  • State reduction from 2D table to 1D rolling array

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate grid-based path count recurrences with obstacle boundary guards.
  • Perform state-space dimension reduction from 2D matrix DP to 1D rolling array.
  • Handle boundary edge cases where starting cell (0,0) or target cell (m-1, n-1) is blocked.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting total number of paths on a 2D matrix with restricted directional moves (right/down).
  • Grid contains static impassable obstacles.
  • Overlapping subproblems where state depends strictly on top and left predecessor cells.

Algorithmic Decision Tree:

  • If movement is strictly monotonic (right/down), use Dynamic Programming over graph search to avoid exponential branch redundancy.
  • Compress 2D DP matrix to 1D rolling array to achieve O(N) space.

Connected Patterns:

Unique Paths (LeetCode 62)Minimum Path Sum (LeetCode 64)Dungeon Game (LeetCode 174)

1. Recursive DFS Backtracking

Intuition

At each cell (r, c), check if within bounds and not an obstacle. Recurse to (r+1, c) and (r, c+1).

Algorithm

  1. Step 1: Check if start cell (0,0) or end cell (m-1, n-1) is 1. If so, return 0.
  2. Step 2: Define helper dfs(r, c).
  3. Step 3: If out of bounds or obstacleGrid[r][c] == 1, return 0.
  4. Step 4: If (r, c) == (m-1, n-1), return 1.
  5. Step 5: Return dfs(r + 1, c) + dfs(r, c + 1).

Recursive DFS Backtracking Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0), (0,1), (0,2), (1,0), (1,1)=OBS, (1,2), (2,0), (2,1), (2,2)=END]
Current operationSTEP 1 OF 6
Start at cell (0,0)
Visual state
Values and pointers at this exact step
pointers
S
0
0
0
↑ start
1
Variables at this step
curr
(0,0)
paths
0
Check / comparison
obstacleGrid[0][0] == 0
Decision / next transition
Explore Branch 1: Right to (0,1).
Why this step matters

Start at cell (0,0). Valid start (val 0). Can branch Right to (0,1) or Down to (1,0).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 int m, n;
6 int dfs(int r, int c, const std::vector<std::vector<int>>& grid) {
7 if (r >= m || c >= n || grid[r][c] == 1) return 0;
8 if (r == m - 1 && c == n - 1) return 1;
9 return dfs(r + 1, c, grid) + dfs(r, c + 1, grid);
10 }
11public:
12 int uniquePathsWithObstacles(const std::vector<std::vector<int>>& obstacleGrid) {
13 if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
14 m = obstacleGrid.size();
15 n = obstacleGrid[0].size();
16 return dfs(0, 0, obstacleGrid);
17 }
18};
19
20int main() {
21 Solution solver;
22 std::vector<std::vector<int>> grid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
23 std::cout << "Unique Paths: " << solver.uniquePathsWithObstacles(grid) << std::endl; // 2
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^(M + N)) — Time complexity for Recursive DFS Backtracking.
  • Space complexity: O(M + N) — Space complexity for Recursive DFS Backtracking.

Why Brute Force Doesn't Scale:

Recursive DFS without memoization visits 2^(M+N) states due to repeated subproblem recomputation.

For a 20x20 grid, DFS takes over 1011 operations whereas 1D Rolling DP executes in just 400 operations.

2. 2D Dynamic Programming Table

Intuition

A cell's path count is the sum of top cell and left cell path counts, provided the current cell is not an obstacle.

Algorithm

  1. Step 1: If obstacleGrid[0][0] == 1, return 0.
  2. Step 2: Allocate dp[m][n] initialized to 0. Set dp[0][0] = 1.
  3. Step 3: Fill row 0: if obstacleGrid[0][c] == 0, dp[0][c] = dp[0][c-1].
  4. Step 4: Fill col 0: if obstacleGrid[r][0] == 0, dp[r][0] = dp[r-1][0].
  5. Step 5: For r from 1 to m-1 and c from 1 to n-1: if obstacleGrid[r][c] == 0, dp[r][c] = dp[r-1][c] + dp[r][c-1].
  6. Step 6: Return dp[m-1][n-1].

2D Dynamic Programming Table Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dp[0][0]=1, dp[0][1]=1, dp[0][2]=1, dp[1][0]=1, dp[1][1]=0, dp[1][2]=1, dp[2][0]=1, dp[2][1]=1, dp[2][2]=2]
Current operationSTEP 1 OF 6
Initialize dp[3][3]
Visual state
Values and pointers at this exact step
pointers
S
1
1
0
↑ base
1
Variables at this step
dp00
1
Check / comparison
dp[0][0] = 1
Decision / next transition
Fill row 0 and col 0 while no obstacle encountered.
Why this step matters

Initialize dp[3][3]. Base case: dp[0][0] = 1 (start cell is unblocked).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int uniquePathsWithObstacles(const std::vector<std::vector<int>>& obstacleGrid) {
7 if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
8 int m = obstacleGrid.size(), n = obstacleGrid[0].size();
9 std::vector<std::vector<long long>> dp(m, std::vector<long long>(n, 0));
10 dp[0][0] = 1;
11
12 for (int c = 1; c < n; ++c) {
13 if (obstacleGrid[0][c] == 0) dp[0][c] = dp[0][c - 1];
14 }
15 for (int r = 1; r < m; ++r) {
16 if (obstacleGrid[r][0] == 0) dp[r][0] = dp[r - 1][0];
17 }
18
19 for (int r = 1; r < m; ++r) {
20 for (int c = 1; c < n; ++c) {
21 if (obstacleGrid[r][c] == 0) {
22 dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
23 }
24 }
25 }
26 return dp[m - 1][n - 1];
27 }
28};
29
30int main() {
31 Solution solver;
32 std::vector<std::vector<int>> grid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
33 std::cout << "2D DP Unique Paths: " << solver.uniquePathsWithObstacles(grid) << std::endl; // 2
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for 2D Dynamic Programming Table.
  • Space complexity: O(M * N) — Space complexity for 2D Dynamic Programming Table.

3. 1D Rolling Array Space Optimization

Intuition

To compute dp[r][c], we only need the value above it (old dp[c]) and the value to its left (new dp[c-1]).

Algorithm

  1. Step 1: Check if start cell obstacleGrid[0][0] == 1; if so, return 0.
  2. Step 2: Allocate 1D array dp of size n filled with 0, set dp[0] = 1.
  3. Step 3: Loop row r from 0 to m-1.
  4. Step 4: Loop col c from 0 to n-1.
  5. Step 5: If obstacleGrid[r][c] == 1, set dp[c] = 0.
  6. Step 6: Else if c > 0, update dp[c] += dp[c - 1].
  7. Step 7: Return dp[n - 1].

1D Rolling Array Space Optimization Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dp[0]=1, dp[1]=1, dp[2]=2]
Current operationSTEP 1 OF 6
Allocate 1D array dp[3] initialized to 0
Visual state
Values and pointers at this exact step
pointers
S
1
0
0
0
↑ base
1
2
Variables at this step
dp
[1,0,0]
Check / comparison
dp[0] = 1
Decision / next transition
Initialize rolling DP array.
Why this step matters

Allocate 1D array dp[3] initialized to 0. Base case: dp[0] = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int uniquePathsWithObstacles(const std::vector<std::vector<int>>& obstacleGrid) {
7 if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
8 int m = obstacleGrid.size();
9 int n = obstacleGrid[0].size();
10
11 std::vector<long long> dp(n, 0);
12 dp[0] = 1;
13
14 for (int r = 0; r < m; ++r) {
15 for (int c = 0; c < n; ++c) {
16 if (obstacleGrid[r][c] == 1) {
17 dp[c] = 0; // Obstacle blocks path
18 } else if (c > 0) {
19 dp[c] += dp[c - 1]; // Add ways from left
20 }
21 }
22 }
23
24 return dp[n - 1];
25 }
26};
27
28int main() {
29 Solution solver;
30 std::vector<std::vector<int>> g1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
31 std::cout << "Test 1: " << solver.uniquePathsWithObstacles(g1) << std::endl; // 2
32
33 std::vector<std::vector<int>> g2 = {{0, 1}, {0, 0}};
34 std::cout << "Test 2: " << solver.uniquePathsWithObstacles(g2) << std::endl; // 1
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for 1D Rolling Array Space Optimization.
  • Space complexity: O(N) — Space complexity for 1D Rolling Array Space Optimization.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive DFSO(2^(M + N))O(M + N)Recursively branch down and right from (0,0) until reaching (m-1, n-1) or hitting an obstacle.Repeatedly computes identical sub-grids exponentially.
2.Better — 2D Dynamic ProgrammingO(M * N)O(M * N)Maintain an M x N table dp[r][c] = dp[r-1][c] + dp[r][c-1] setting obstacles to 0.Matrix memory allocation.
3.Optimal — 1D Rolling Array DPOptimalO(M * N)O(N)Compress DP table into a single 1D array of size N. Update in-place: dp[c] = obstacle ? 0 : dp[c] + dp[c-1].None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Start cell blocked (obstacleGrid[0][0] == 1) — Return 0 immediately.
  • Target cell blocked (obstacleGrid[m-1][n-1] == 1) — Cannot finish, returns 0.
  • Single cell open [[0]] — Returns 1.
  • Single row/column with middle obstacle — All cells after obstacle become 0 paths.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can the 2D DP table be reduced to a 1D array of size N in Unique Paths II?

2.What is the return value if obstacleGrid[0][0] == 1?

3.What is the space complexity of the optimal rolling array approach in Unique Paths II?

Back to DSA Sheet