easyRecursionPattern: Recursion
Count Paths in Grid Solution
Problem Statement
Given a 2D grid of size m x n, where each cell can be either an obstacle or an empty space, find the number of unique paths from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1). You can only move down or right at any point in time. An obstacle is represented by 1, and an empty space is represented by 0. If the starting cell or the ending cell contains an obstacle, there are no valid paths.
Examples
Example 1:
Input:grid = [[0,0,0],[0,1,0],[0,0,0]]
Output:0
Explanation: There are two possible paths from (0,0) to (2,2):
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Note that the path cannot pass through the obstacle at (1,1).
Example 2:
Input:grid = [[0,1],[0,0]]
Output:0
Explanation: The only possible path is Down -> Right. The path cannot go Right first due to the obstacle at (0,1).
Example 3:
Input:grid = [[1,0],[0,0]]
Output:0
Explanation: The starting cell (0,0) is an obstacle, so there are no paths.
Constraints
- 1 <= m, n <= 100
- grid[i][j] is either 0 or 1.
- grid[0][0] == 0 (unless m=1, n=1 and grid[0][0] is an obstacle which should return 0)
- grid[m-1][n-1] == 0 (unless m=1, n=1 and grid[0][0] is an obstacle which should return 0)
Time: O(m*n) Space: O(m*n)
This problem can be efficiently solved using dynamic programming. We can create a DP table of the same dimensions as the grid. dp[i][j] will store the number of unique paths to reach cell (i, j). The recurrence relation is dp[i][j] = dp[i-1][j] + dp[i][j-1] if grid[i][j] is not an obstacle. Base cases are handled for the first row and column, and obstacles reset the path count to 0.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def unique_paths_with_obstacles(obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
return 0
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = 1
# Fill first column
for i in range(1, m):
if obstacleGrid[i][0] == 0 and dp[i-1][0] == 1:
dp[i][0] = 1
else:
dp[i][0] = 0
# Fill first row
for j in range(1, n):
if obstacleGrid[0][j] == 0 and dp[0][j-1] == 1:
dp[0][j] = 1
else:
dp[0][j] = 0
# Fill the rest of the DP table
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = 0
return dp[m-1][n-1]