mediumGraphsPattern: BFS
Minimum Path Sum in Grid Solution
Problem Statement
Given an m x n 2D grid filled with non-negative numbers, find a path from the top-left cell to the bottom-right cell such that the sum of all numbers along the path is minimized. You can only move either down or right at any point in time.
Examples
Example 1:
Input:{"grid":[[1,3,1],[1,5,1],[4,2,1]]}
Output:{"minSum":7}
Explanation: The path 1→3→1→1→1 minimizes the sum. The total sum is 1 + 3 + 1 + 1 + 1 = 7.
Example 2:
Input:{"grid":[[1,2,3],[4,5,6]]}
Output:{"minSum":12}
Explanation: The path 1→2→3→6 minimizes the sum. The total sum is 1 + 2 + 3 + 6 = 12.
Example 3:
Input:{"grid":[[5]]}
Output:{"minSum":5}
Explanation: The path is just the single cell. The total sum is 5.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
Time: O(m*n) Space: O(1)
This problem can be solved efficiently using dynamic programming. We can create a DP table (or use the grid itself) where dp[i][j] represents the minimum path sum to reach cell (i, j). The recurrence relation is dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), with base cases for the first row and first column.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def min_path_sum(grid):
m = len(grid)
n = len(grid[0])
# Create a DP table with the same dimensions as the grid
dp = [[0 for _ in range(n)] for _ in range(m)]
# Initialize the top-left cell
dp[0][0] = grid[0][0]
# Fill the first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# Fill the first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Fill the rest of the DP table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
# The minimum path sum is in the bottom-right cell
return dp[m-1][n-1]