Description:
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.
Examples:
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: 1Solution in Python:
To solve the problem of finding the number of unique paths for a robot to reach the bottom-right corner of a grid with obstacles, we can use a dynamic programming approach.
Steps to Solve the Problem:
- Define the Problem in Terms of Subproblems:
- We need to calculate the number of ways to reach each cell
(i, j)from the starting cell(0, 0)while avoiding obstacles. - If a cell has an obstacle (
1), the number of ways to reach that cell is0. - The robot can only move right or down, so the number of ways to reach cell
(i, j)is the sum of the number of ways to reach cell(i-1, j)(from the cell above) and cell(i, j-1)(from the cell to the left), provided those cells are not obstacles.
- We need to calculate the number of ways to reach each cell
- Initialize the Base Cases:
- The starting cell
(0, 0)can only be reached if it is not an obstacle. - If any cell in the first row or first column is an obstacle, all cells beyond it in that row or column are unreachable.
- The starting cell
- Create and Populate the DP Table:
- Create a 2D array
dpwheredp[i][j]represents the number of unique paths to cell(i, j). - Iterate through the grid, and for each cell
(i, j), updatedp[i][j]based on the values from the cell above it and the cell to the left of it, while considering obstacles.
- Create a 2D array
- Return the Result:
- The value at
dp[m-1][n-1]will give us the number of unique paths to the bottom-right corner of the grid.
- The value at
Python
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# Get the dimensions of the grid
m, n = len(obstacleGrid), len(obstacleGrid[0])
# If the starting or ending point is an obstacle, return 0
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
return 0
# Create a 2D dp array initialized to 0
dp = [[0] * n for _ in range(m)]
# Initialize the starting point
dp[0][0] = 1
# Fill the first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
# Fill the first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
# Fill 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 the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1]Detailed Explanation:
- Initialization:
m, n = len(obstacleGrid), len(obstacleGrid[0])gets the dimensions of the grid.- The condition
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1checks if the start or end point is an obstacle and returns0if true. dp = [[0] * n for _ in range(m)]creates anm x ngrid initialized to0.
- Setting Up the Starting Point:
dp[0][0] = 1initializes the starting point as reachable if it is not an obstacle.
- Filling the First Row and Column:
- The loops
for j in range(1, n): dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0andfor i in range(1, m): dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0fill the first row and column while considering obstacles.
- The loops
- Filling the DP Table:
- The nested loop
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] = 0computes the number of ways to reach each cell(i, j)by summing the ways to reach the cell from above (dp[i-1][j]) and from the left (dp[i][j-1]), while considering obstacles.
- The nested loop
- Result:
return dp[m-1][n-1]returns the value at the bottom-right corner of the grid, which represents the number of unique paths to that cell.
This approach ensures that we efficiently compute the number of unique paths using dynamic programming while avoiding obstacles in O(m * n) time complexity, which is suitable given the problem constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// Get the dimensions of the grid
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// If the starting or ending point is an obstacle, return 0
if (obstacleGrid[0][0] === 1 || obstacleGrid[m-1][n-1] === 1) {
return 0;
}
// Create a 2D dp array initialized to 0
const dp = Array.from({ length: m }, () => Array(n).fill(0));
// Initialize the starting point
dp[0][0] = 1;
// Fill the first row
for (let j = 1; j < n; j++) {
dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j-1] : 0;
}
// Fill the first column
for (let i = 1; i < m; i++) {
dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i-1][0] : 0;
}
// Fill the dp table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (obstacleGrid[i][j] === 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
// Return the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1];
};Solution in Java:
Java
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// Get the dimensions of the grid
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// If the starting or ending point is an obstacle, return 0
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
return 0;
}
// Create a 2D dp array initialized to 0
int[][] dp = new int[m][n];
// Initialize the starting point
dp[0][0] = 1;
// Fill the first row
for (int j = 1; j < n; j++) {
dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j-1] : 0;
}
// Fill the first column
for (int i = 1; i < m; i++) {
dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i-1][0] : 0;
}
// Fill the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
// Return the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1];
}
}Solution in C#:
C#
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
// Get the dimensions of the grid
int m = obstacleGrid.Length;
int n = obstacleGrid[0].Length;
// If the starting or ending point is an obstacle, return 0
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
return 0;
}
// Create a 2D dp array initialized to 0
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) {
dp[i] = new int[n];
}
// Initialize the starting point
dp[0][0] = 1;
// Fill the first row
for (int j = 1; j < n; j++) {
dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j-1] : 0;
}
// Fill the first column
for (int i = 1; i < m; i++) {
dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i-1][0] : 0;
}
// Fill the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else {
dp[i][j] = 0;
}
}
}
// Return the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1];
}
}