How do you solve Unique Paths II on LeetCode?

Unique Paths II (LeetCode #63) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m*n) time complexity and O(m*n) space complexity. Key insight: Dynamic programming is essential for optimizing recursive problems with overlapping subproblems.

What is the time complexity of Unique Paths II?

The optimal solution for Unique Paths II runs in O(m*n) time and uses O(m*n) space. This complexity is due to the need to fill a 2D DP array of size m*n, where each cell is processed once.

What is the brute force solution for Unique Paths II?

The brute force approach for Unique Paths II is Brute Force, with O(2^(m+n)) time complexity and O(m+n) space complexity. The brute force approach explores all possible paths from the top-left to the bottom-right corner of the grid. It recursively checks each possible move (down or right) until it reaches the destination or hits an obstacle. The optimal Optimal Solution approach improves this to O(m*n).

What algorithm or data structure is used to solve Unique Paths II?

Unique Paths II uses the following concepts: Array, Dynamic Programming, Matrix. The recommended patterns to study are: Dynamic Programming, Grid Traversal.

What are the interview tips for Unique Paths II?

Always clarify the problem constraints and edge cases before diving into coding. Explain your thought process and approach before writing code to ensure clarity. Practice explaining your code as you write it, as this simulates the interview environment.

What are common mistakes when solving Unique Paths II?

Forgetting to handle obstacles correctly in the DP table. Not initializing the starting point properly, especially when it is an obstacle.

#63

Unique Paths II

Medium

ArrayDynamic ProgrammingMatrixDynamic ProgrammingGrid Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^(m+n))	O(m*n)
Space	O(m+n)	O(m*n)

💡

Intuition

Time O(m*n)Space O(m*n)

The optimal solution uses dynamic programming to build a table that keeps track of the number of unique paths to each cell. By using previously computed values, we avoid redundant calculations and significantly reduce the time complexity.

⚙️

Algorithm

4 steps

1Step 1: Create a 2D DP array of the same size as the grid initialized to 0.
2Step 2: Set dp[0][0] to 1 if the starting cell is not an obstacle.
3Step 3: Iterate through each cell in the grid. If the cell is not an obstacle, update dp[i][j] as the sum of dp[i-1][j] and dp[i][j-1] (if within bounds).
4Step 4: Return the value at dp[m-1][n-1] as the result.

solution.py14 lines

1def uniquePathsWithObstacles(grid):
2    m, n = len(grid), len(grid[0])
3    dp = [[0] * n for _ in range(m)]
4    dp[0][0] = 1 if grid[0][0] == 0 else 0
5    for i in range(m):
6        for j in range(n):
7            if grid[i][j] == 1:
8                dp[i][j] = 0
9            else:
10                if i > 0:
11                    dp[i][j] += dp[i - 1][j]
12                if j > 0:
13                    dp[i][j] += dp[i][j - 1]
14    return dp[m - 1][n - 1]

ℹ

Complexity note: This complexity is due to the need to fill a 2D DP array of size m*n, where each cell is processed once.

1Dynamic programming is essential for optimizing recursive problems with overlapping subproblems.
2Understanding how to build a DP table can greatly simplify pathfinding problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.