Using dynamic programming, we can track the number of unique paths to each cell in the grid. Initialize a DP matrix of the same dimensions as the grid. If a cell contains an obstacle (value of 1), it will have 0 paths. Start from the top-left corner and accumulate the number of paths by adding the values from the cell above and the cell to the left, if they exist, taking into account obstacles.
Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.
1def uniquePathsWithObstacles(obstacleGrid):
2 m, n = len(obstacleGrid), len(obstacleGrid[0])
3 dp = [[0] * n for _ in range(m)]
4
5 for i in range(m):
6 for j in range(n):
7 if obstacleGrid[i][j] == 1:
8 dp[i][j] = 0
9 elif i == 0 and j == 0:
10 dp[i][j] = 1
11 else:
12 dp[i][j] = (dp[i-1][j] if i > 0 else 0) + (dp[i][j-1] if j > 0 else 0)
13
14 return dp[-1][-1]
15Python solution creates a DP matrix to calculate unique paths considering obstacles, starting from the first cell and iteratively processing each cell's possible paths.
Instead of using a full 2D DP array, we can optimize space by maintaining just a single row of size `n` to hold the number of paths to positions in the current row. Iterate over the grid, and update path counts by only storing the results for the current row, using the previous row information to calculate paths.
Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.
1var uniquePathsWithObstacles = function(obstacleGrid) {
2 let m = obstacleGrid.length;
3 let n = obstacleGrid[0].length;
4 let dp = Array(n).fill(0);
5 dp[0] = obstacleGrid[0][0] === 0 ? 1 : 0;
6
7 for (let i = 0; i < m; i++) {
8 for (let j = 0; j < n; j++) {
9 if (obstacleGrid[i][j] === 1) {
10 dp[j] = 0;
11 } else if (j > 0) {
12 dp[j] += dp[j - 1];
13 }
14 }
15 }
16 return dp[n - 1];
17};
18JavaScript solution optimizes memory use by compressing the path calculation into a one-dimensional array adjusted continuously per grid row, circumventing obstacle blocks effectively.