grid47 Exploring patterns and algorithms
Oct 31, 2024
6 min read
Solution to LeetCode 63: Unique Paths II Problem
A robot starts at the top-left corner of an m x n grid and needs to reach the bottom-right corner. The grid contains obstacles (marked as 1) and empty cells (marked as 0). The robot can only move down or right and cannot pass through cells with obstacles. Determine the number of unique paths to the destination.
Problem
Approach
Steps
Complexity
Input: An integer 2D array grid where grid[i][j] is either 0 (empty) or 1 (obstacle).
• Explanation: There is only one unique path that avoids obstacles.
Approach: Use a dynamic programming approach to calculate the total paths, where cells with obstacles are marked as 0.
Observations:
• The problem requires handling obstacles, making it different from the regular unique paths problem.
• Cells with obstacles contribute 0 paths and block traversal.
• Dynamic programming can be adapted by marking obstacle cells as 0.
Steps:
• Initialize a DP table with dimensions m x n, set dp[0][0] = 1 if the starting cell is empty.
• Iterate through the grid; for each cell, calculate dp[i][j] = dp[i-1][j] + dp[i][j-1] if grid[i][j] is empty.
• Set dp[i][j] = 0 for cells with obstacles.
• Return dp[m-1][n-1] as the total number of paths.
Empty Inputs:
• Not applicable as input is guaranteed.
Large Inputs:
• Maximum grid size with m = 100 and n = 100, with scattered obstacles.
Special Values:
• A grid where the start or end cell is blocked (grid[0][0] or grid[m-1][n-1] = 1).
Constraints:
• Ensure the algorithm handles all obstacles efficiently.
intuniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
// Handle the case where the starting cell is an obstacle
if (obstacleGrid[0][0] ==1) {
return0;
}
// Initialize the first cell as 1, as there's only one way to reach it
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 rest of 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];
}
}
}
return dp[m -1][n -1];
}
This line declares a function named `uniquePathsWithObstacles` that takes a 2D vector `obstacleGrid` representing the grid with obstacles as input and returns the number of unique paths.
2 : Get Grid Dimensions
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
This line gets the dimensions of the grid, `m` for rows and `n` for columns.
3 : Initialize DP Table
vector<vector<int>> dp(m, vector<int>(n, 0));
This line initializes a 2D DP table `dp` of size `m x n` to store the number of unique paths to reach each cell. All elements are initially set to 0.
4 : Handle Starting Obstacle
if (obstacleGrid[0][0] ==1) {
return0;
}
This condition checks if the starting cell is an obstacle. If so, there are no possible paths, so the function returns 0.
5 : Initialize Starting Cell
dp[0][0] =1;
If the starting cell is not an obstacle, it's initialized with 1, as there's only one way to reach it.
This loop fills the first row of the DP table. For each cell, if it's not an obstacle, the number of paths to reach it is the same as the number of paths to reach the cell to its left. Otherwise, it's 0.
7 : Fill First Column
for (int i =1; i < m; i++) {
dp[i][0] = obstacleGrid[i][0] ==0? dp[i -1][0] :0;
}
This loop fills the first column of the DP table. For each cell, if it's not an obstacle, the number of paths to reach it is the same as the number of paths to reach the cell above it. Otherwise, it's 0.
8 : Fill the Rest of 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];
}
}
}
This nested loop fills the rest of the DP table. For each cell `(i, j)` that is not an obstacle, the number of paths to reach it is the sum of the number of paths to reach the cell above it and the cell to its left.
9 : Return the Bottom-Right Corner Value
return dp[m -1][n -1];
After filling the DP table, the function returns the value at the bottom-right corner `dp[m - 1][n - 1]`, which represents the total number of unique paths from the top-left to the bottom-right corner.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: Each cell is visited exactly once.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The DP table requires O(m * n) space.
