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.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner:
Example 2:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Can you solve this problem efficiently, considering space and time complexity? What are the edge cases we should take into account?
You are given an m x n
integer array grid
representing a grid with obstacles. The robot starts at the top-left corner (0, 0) and tries to reach the bottom-right corner (m-1, n-1). The robot can only move down or right. Obstacles are marked as 1, and empty spaces are marked as 0. The task is to find the number of unique paths the robot can take without stepping on any obstacles.
A simple approach is to use recursion. We can define a recursive function that takes the current position (row, col) as input. If the current position is the destination, we return 1 (found a path). If the current position is out of bounds or is an obstacle, we return 0 (invalid path). Otherwise, we recursively call the function for the 'down' and 'right' moves and sum the results.
We can optimize the recursive approach using dynamic programming. Instead of recomputing the number of paths for each cell, we can store the results in a table (DP table). The DP table dp[i][j]
stores the number of unique paths to reach cell (i, j).
Initialize a DP table of size m x n
with 0s.
If the starting cell (0, 0) is not an obstacle, set dp[0][0] = 1
.
Iterate through the grid, and for each cell (i, j):
dp[i][j] = 0
.dp[i][j] = dp[i-1][j] + dp[i][j-1]
(sum of paths from the top and left cells).Consider edge cases for the first row and first column to avoid out-of-bounds access.
The result is stored in dp[m-1][n-1]
.
def uniquePathsWithObstacles(obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# If the starting cell has an obstacle, there are no paths.
if obstacleGrid[0][0] == 1:
return 0
# Initialize DP table
dp = [[0] * n for _ in range(m)]
# Starting cell
dp[0][0] = 1
# Fill the first row
for j in range(1, n):
if obstacleGrid[0][j] == 0:
dp[0][j] = dp[0][j-1]
else:
dp[0][j] = 0
# Fill the first column
for i in range(1, m):
if obstacleGrid[i][0] == 0:
dp[i][0] = dp[i-1][0]
else:
dp[i][0] = 0
# Fill the rest of the 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]