Unique Paths in a Grid with Obstacles

January 8, 2024

medium

Problem #

Given a m x n grid filled with non-negative numbers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Some cells might be obstacles where the robot cannot enter. These cells are marked with a -1. Other cells contain integers representing the cost of passing through them. Find the minimum cost to reach the bottom right corner.

Example: #

Input:

grid = [
  [1,  3,  1],
  [-1, 5,  0],
  [4,  2,  1]
]

Output: 7 (The path is 1→3→1→0→1 which costs 7.)

Solution #

The problem can be solved using dynamic programming. We will create a 2D array dp where dp[i][j] represents the minimum cost to reach cell (i, j) from the top left corner. If a cell is an obstacle, we set its cost to be infinity, as it is not reachable.

Algorithm Steps: #

Initialize a 2D array dp of the same size as the grid.
Set dp[0][0] to grid[0][0] if it’s not an obstacle, otherwise set to infinity.
For each cell (i, j) in dp, calculate dp[i][j] as the minimum of dp[i-1][j] and dp[i][j-1] added to grid[i][j], if grid[i][j] is not an obstacle.
The answer will be dp[m-1][n-1] if it’s not infinity.

Code in Python: #

def minPathSum(grid):
    if not grid or grid[0][0] == -1:
        return -1
    
    m, n = len(grid), len(grid[0])
    dp = [[float('inf')] * n for _ in range(m)]
    dp[0][0] = grid[0][0] if grid[0][0] != -1 else float('inf')

    for i in range(1, m):
        if grid[i][0] != -1:
            dp[i][0] = dp[i-1][0] + grid[i][0]

    for j in range(1, n):
        if grid[0][j] != -1:
            dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] != -1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1] if dp[m-1][n-1] != float('inf') else -1

Code Analysis #

Function Definition:
```
def minPathSum(grid):
```
This defines a function minPathSum that takes grid as its input. grid is a 2D list of integers where some cells might have a value of -1, indicating an obstacle.
Initial Checks:
```
if not grid or grid[0][0] == -1:
    return -1
```
This checks if the grid is empty or if the starting cell (top-left corner) is an obstacle. If either is true, the function returns -1 indicating that there is no valid path.
Grid Dimensions:
```
m, n = len(grid), len(grid[0])
```
Here, m and n are set to the number of rows and columns of the grid, respectively.
Initialize DP Array:
```
dp = [[float('inf')] * n for _ in range(m)]
dp[0][0] = grid[0][0] if grid[0][0] != -1 else float('inf')
```
A 2D list dp of size m x n is created, initially filled with float('inf'), which represents an unreachable or very high cost. The top-left cell dp[0][0] is set to the value of grid[0][0] if it’s not an obstacle; otherwise, it remains float('inf').
Filling First Column of DP Array:
```
for i in range(1, m):
    if grid[i][0] != -1:
        dp[i][0] = dp[i-1][0] + grid[i][0]
```
This loop fills the first column of the dp array. For each cell in the first column, if it’s not an obstacle, the cost to reach that cell is the cost to reach the cell above it plus the cell’s own cost.
Filling First Row of DP Array:
```
for j in range(1, n):
    if grid[0][j] != -1:
        dp[0][j] = dp[0][j-1] + grid[0][j]
```
Similarly, this loop fills the first row of the dp array. It accumulates the cost along the top row, considering obstacles.
Populating the Rest of the DP Array:
```
for i in range(1, m):
    for j in range(1, n):
        if grid[i][j] != -1:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
```
This nested loop fills the rest of the dp array. For each cell (i, j), it calculates the minimum cost to reach that cell either from the cell directly above it (dp[i-1][j]) or from the cell to its left (dp[i][j-1]), then adds the cost of the current cell grid[i][j].
Returning the Result:
```
return dp[m-1][n-1] if dp[m-1][n-1] != float('inf') else -1
```
Finally, the function returns the value of dp[m-1][n-1], which represents the minimum cost to reach the bottom-right corner of the grid. If this value is float('inf'), it means the bottom-right corner is unreachable, and the function returns -1.

Overall, the code uses dynamic programming to build up a solution iteratively, taking into account the obstacles and minimizing the total cost along the path.

Time Complexity: #

O(mn), where m is the number of rows and n is the number of columns in the grid.

Space Complexity: #

O(mn), for the 2D dp array.