63. Unique Paths II Solution & Explanation

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Q: 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.

The problem

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 * 10⁹.

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.

Python

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = (dp[i-1][j] if i > 0 else 0) + (dp[i][j-1] if j > 0 else 0)
    
    return dp[-1][-1]

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

C++

#include <vector>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
            }
        }
    }

    return dp[m-1][n-1];
}

JavaScript

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array.from({length: m}, () => Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0;
            } else if (i === 0 && j === 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
            }
        }
    }

    return dp[m-1][n-1];
};

#include <stdio.h>

int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
    int dp[m][n];
    
    // Initialize DP table
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1];
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
}

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        int[,] dp = new int[m, n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i, j] = 0;
                } else if (i == 0 && j == 0) {
                    dp[i, j] = 1;
                } else {
                    dp[i, j] = (i > 0 ? dp[i-1, j] : 0) + (j > 0 ? dp[i, j-1] : 0);
                }
            }
        }

        return dp[m - 1, n - 1];
    }
}

Python solution creates a DP matrix to calculate unique paths considering obstacles, starting from the first cell and iteratively processing each cell's possible paths.

Complexity

Time Complexity: O(m * n), as we iterate through entire grid.
Space Complexity: O(m * n), due to the use of 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.

Python

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0] * n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]
    return dp[-1]

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

C++

#include <vector>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    vector<int> dp(n, 0);
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

JavaScript

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let dp = Array(n).fill(0);
    dp[0] = obstacleGrid[0][0] === 0 ? 1 : 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
};

#include <stdio.h>

int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
    int dp[n];
    memset(dp, 0, sizeof(dp));
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

Python solution applies space optimization by limiting storage to a single array retaining path counts, efficiently managing obstacle-negotiated computations.

Complexity

Time Complexity: O(m * n), iterating over all grid cells.
Space Complexity: O(n), single-dimensional path tracking per row.

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.

TypeScript

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const f: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
    const dfs = (i: number, j: number): number => {
        if (i >= m || j >= n || obstacleGrid[i][j] === 1) {
            return 0;
        }
        if (i === m - 1 && j === n - 1) {
            return 1;
        }
        if (f[i][j] === -1) {
            f[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
        }
        return f[i][j];
    };
    return dfs(0, 0);
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m || j >= n || obstacleGrid[i][j] == 1 {
			return 0
		}
		if i == m-1 && j == n-1 {
			return 1
		}
		if f[i][j] == -1 {
			f[i][j] = dfs(i+1, j) + dfs(i, j+1)
		}
		return f[i][j]
	}
	return dfs(0, 0)
}

Rust

impl Solution {
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        let mut f = vec![vec![-1; n]; m];
        Self::dfs(0, 0, &obstacle_grid, &mut f)
    }

    fn dfs(i: usize, j: usize, obstacle_grid: &Vec<Vec<i32>>, f: &mut Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        if i >= m || j >= n || obstacle_grid[i][j] == 1 {
            return 0;
        }
        if i == m - 1 && j == n - 1 {
            return 1;
        }
        if f[i][j] != -1 {
            return f[i][j];
        }
        let down = Self::dfs(i + 1, j, obstacle_grid, f);
        let right = Self::dfs(i, j + 1, obstacle_grid, f);
        f[i][j] = down + right;
        f[i][j]
    }
}

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.

TypeScript

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const f = Array.from({ length: m }, () => Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        if (obstacleGrid[i][0] === 1) {
            break;
        }
        f[i][0] = 1;
    }
    for (let i = 0; i < n; i++) {
        if (obstacleGrid[0][i] === 1) {
            break;
        }
        f[0][i] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                continue;
            }
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	f := make([][]int, m)
	for i := 0; i < m; i++ {
		f[i] = make([]int, n)
	}
	for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
		f[i][0] = 1
	}
	for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
		f[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 0 {
				f[i][j] = f[i-1][j] + f[i][j-1]
			}
		}
	}
	return f[m-1][n-1]
}

Rust

impl Solution {
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        let mut f = vec![vec![0; n]; m];
        for i in 0..n {
            if obstacle_grid[0][i] == 1 {
                break;
            }
            f[0][i] = 1;
        }
        for i in 0..m {
            if obstacle_grid[i][0] == 1 {
                break;
            }
            f[i][0] = 1;
        }
        for i in 1..m {
            for j in 1..n {
                if obstacle_grid[i][j] == 1 {
                    continue;
                }
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        f[m - 1][n - 1]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(m * n), as we iterate through entire grid. Space Complexity: O(m * n), due to the use of dp table.
Space Optimized Dynamic Programming	Time Complexity: O(m * n), iterating over all grid cells. Space Complexity: O(n), single-dimensional path tracking per row.
Memoization Search	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When 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 Programming	O(m*n)	O(n)	When memory matters or when demonstrating DP state compression

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.

Unique Paths II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Space Optimized Dynamic Programming

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Unique Paths II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Space Optimized Dynamic Programming

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems