Unique Paths II
Problem 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.
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: 1
Constraints:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
Solve it on LeetCode
Approaches
1. Recursive Backtracking
Intuition:
The recursive backtracking approach is a brute force method where we explore every possible path from the starting point to the destination, taking into account obstacles. This involves trying to move right and down at each step recursively.
Code:
- Time Complexity: O(2^(m+n)) — Each point can either move right or down, resulting in exponential time.
- Space Complexity: O(m+n) — Recursive stack space.
2. Memoization
Intuition:
Memoization will be used to store results of already computed paths for each grid cell to avoid redundant calculations. This is an optimization to the recursive approach.
Code:
- Time Complexity: O(m*n) — Each cell is computed once.
- Space Complexity: O(m*n) + O(m+n) — Space for memo array and recursion stack.
3. Dynamic Programming
Intuition:
Using a table to systematically compute the number of unique paths to each cell, considering obstacles.
Code:
- Time Complexity: O(m*n) — We iterate through each cell once.
- Space Complexity: O(m*n) — Space for the dp array.
4. Dynamic Programming with Space Optimization
Intuition:
By leveraging the fact that we only need the previous row and previous column to calculate the current cell's paths, we can optimize the space to O(n) using a single array.
Code:
- Time Complexity: O(m*n) — We iterate through each cell once.
- Space Complexity: O(n) — Space for the 1-D dp array.