Unique Paths in a Grid with Obstacles
January 8, 2024
Problem #
Given a m x n
grid filled with nonnegative 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]
togrid[0][0]
if it’s not an obstacle, otherwise set to infinity.  For each cell
(i, j)
indp
, calculatedp[i][j]
as the minimum ofdp[i1][j]
anddp[i][j1]
added togrid[i][j]
, ifgrid[i][j]
is not an obstacle.  The answer will be
dp[m1][n1]
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[i1][0] + grid[i][0]
for j in range(1, n):
if grid[0][j] != 1:
dp[0][j] = dp[0][j1] + 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[i1][j], dp[i][j1]) + grid[i][j]
return dp[m1][n1] if dp[m1][n1] != float('inf') else 1
Code Analysis #

Function Definition:
def minPathSum(grid):
This defines a function
minPathSum
that takesgrid
as its input.grid
is a 2D list of integers where some cells might have a value of1
, 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 (topleft 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
andn
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 sizem x n
is created, initially filled withfloat('inf')
, which represents an unreachable or very high cost. The topleft celldp[0][0]
is set to the value ofgrid[0][0]
if it’s not an obstacle; otherwise, it remainsfloat('inf')
. 
Filling First Column of DP Array:
for i in range(1, m): if grid[i][0] != 1: dp[i][0] = dp[i1][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][j1] + 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[i1][j], dp[i][j1]) + 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[i1][j]
) or from the cell to its left (dp[i][j1]
), then adds the cost of the current cellgrid[i][j]
. 
Returning the Result:
return dp[m1][n1] if dp[m1][n1] != float('inf') else 1
Finally, the function returns the value of
dp[m1][n1]
, which represents the minimum cost to reach the bottomright corner of the grid. If this value isfloat('inf')
, it means the bottomright corner is unreachable, and the function returns1
.
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.