Skip to main content
Talentd

Unique Paths II - Solution & Explanation

MediumArrayDynamic ProgrammingMatrix27 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

You are given an m x n integer array grid. 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 grid. 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 * 109.

 

Example 1:

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 above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

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

 

Constraints:

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

Approach Overview

Problem Overview: Given an m x n grid where some cells contain obstacles, count how many unique paths exist from the top-left corner to the bottom-right corner. You can only move right or down, and any cell marked as an obstacle blocks the path.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

This approach builds a 2D DP table where dp[i][j] stores the number of ways to reach cell (i, j). If the current cell is not an obstacle, the number of paths equals the sum of paths from the top cell dp[i-1][j] and the left cell dp[i][j-1]. If the cell contains an obstacle, its value becomes 0 because no path can pass through it. You iterate row by row through the matrix, updating the DP table using previously computed values. This approach clearly models the recurrence relation and is the easiest way to reason about the state transitions.

Approach 2: Space Optimized Dynamic Programming (O(m*n) time, O(n) space)

The DP relation only depends on the current row and the previous row, so a full m x n table is unnecessary. Instead, maintain a single array of size n where each element represents the number of ways to reach that column in the current row. While iterating through the grid, update the array in place: if a cell contains an obstacle, set the value to 0; otherwise add the value from the left neighbor dp[j] += dp[j-1]. This technique reduces memory usage while preserving the same recurrence used in dynamic programming. The logic still processes the grid row by row using standard array iteration.

Recommended for interviews: The standard 2D dynamic programming solution demonstrates clear understanding of the recurrence and boundary conditions, so it is the safest explanation during interviews. After presenting it, optimizing to a single-row DP array shows deeper understanding of memory optimization and DP state compression.

Approach 1: Dynamic Programming Approach

Using dynamic programming, we can track the number of unique paths to each cell in the grid. Initialize a DP matrix of the same dimensions as the grid. If a cell contains an obstacle (value of 1), it will have 0 paths. Start from the top-left corner and accumulate the number of paths by adding the values from the cell above and the cell to the left, if they exist, taking into account obstacles.

This solution implements a dynamic programming strategy to fill a DP table. Each cell in the DP table represents the number of unique paths to that cell, calculated by summing the possible paths from the left and above cells, unless they contain obstacles.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.

Try this approach in the editor →

Approach 2: Space Optimized Dynamic Programming

Instead of using a full 2D DP array, we can optimize space by maintaining just a single row of size `n` to hold the number of paths to positions in the current row. Iterate over the grid, and update path counts by only storing the results for the current row, using the previous row information to calculate paths.

Optimized C solution utilizes a single-dimension array to save space, updating path counts as it iterates over each grid row while handling obstacles.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j) to represent the number of paths from the grid (i, j) to the grid (m - 1, n - 1). Here, m and n are the number of rows and columns of the grid, respectively.

The execution process of the function dfs(i, j) is as follows:

  • If i \ge m or j \ge n, or obstacleGrid[i][j] = 1, the number of paths is 0;
  • If i = m - 1 and j = n - 1, the number of paths is 1;
  • Otherwise, the number of paths is dfs(i + 1, j) + dfs(i, j + 1).

To avoid redundant calculations, we can use memoization.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Dynamic Programming

We can use a dynamic programming approach by defining a 2D array f, where f[i][j] represents the number of paths from the grid (0,0) to the grid (i,j).

We first initialize all values in the first column and the first row of f, then traverse the other rows and columns with two cases:

  • If obstacleGrid[i][j] = 1, it means the number of paths is 0, so f[i][j] = 0;
  • If obstacleGrid[i][j] = 0, then f[i][j] = f[i - 1][j] + f[i][j - 1].

Finally, return f[m - 1][n - 1].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.

Space Optimized Dynamic Programming

Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.

Memoization Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (2D DP Table)O(m*n)O(m*n)Best for clarity when explaining DP state transitions during interviews
Space Optimized Dynamic ProgrammingO(m*n)O(n)When memory matters or when demonstrating DP state compression

Video Solution

Unique Paths II - Leetcode 63 - Python • NeetCodeIO • 33,090 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Unique Paths II easy or hard?
Unique Paths II is considered a medium-level problem. The base Unique Paths problem is easier, but adding obstacles requires careful DP initialization and handling blocked cells during transitions.
How to solve Unique Paths II in O(n) space?
Use a single row DP array of length n. While iterating through each row, update dp[j] based on dp[j] (top) and dp[j-1] (left). If the current cell is an obstacle, reset dp[j] to 0. This keeps the time complexity O(m*n) while reducing memory to O(n).
What is the best approach for Unique Paths II?
Dynamic Programming is the most reliable approach. Create a DP grid where each cell stores the number of ways to reach that position while skipping obstacle cells. The transition adds paths from the top and left neighbors. This runs in O(m*n) time and is the expected interview solution.
What data structure is used in Unique Paths II?
The solution mainly uses arrays to build a dynamic programming table. Either a 2D array stores paths for every grid cell or a 1D array compresses the DP state to reduce space while iterating through the matrix.
What is the time complexity of Unique Paths II?
The standard dynamic programming solution runs in O(m*n) time because each cell of the grid is processed exactly once. The space complexity is O(m*n) for the full DP table or O(n) when using the space-optimized DP array.
Unique Paths II Python or Java solution approach?
Both Python and Java implementations follow the same DP recurrence. Create a DP array, initialize the start cell if it is not an obstacle, and iterate through the grid updating values using paths from the top and left cells. Time complexity remains O(m*n).
Is Unique Paths II asked at Google, Amazon, or Meta interviews?
Grid dynamic programming problems similar to Unique Paths II frequently appear in interviews at companies like Amazon, Google, and Meta. Interviewers use them to test DP reasoning, handling obstacles, and understanding of state transitions in matrix traversal problems.

Ready to solve this problem?

Practice Unique Paths II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Path Cost in a Grid

Next

Paths in Matrix Whose Sum Is Divisible by K