64. Minimum Path Sum
Model: qwen3.5:9b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 56.5%
Problem Breakdown
We are given an m x n grid of non-negative integers representing costs at each cell. The goal is to find the path from the top-left (0, 0) to bottom-right (m-1, n-1) that yields the minimum total sum of numbers encountered along the way.
Key Constraints & Rules:
- Movement: We can only move Down or Right at any step. This restricts us and prevents cycles (no backtracking).
- Inputs: A 2D list
grid. Dimensions are between 1 and 200. Values are . - Outputs: An integer representing the minimum path sum.
Implicit Edge Cases to Consider:
- Single cell grid (): The answer is simply
grid[0][0]. - Single row or single column: There is only one valid path (straight line), so we just accumulate sums along that dimension.
- Overflow: Since max value per cell is 100 and grid size is , the maximum possible sum fits comfortably within a standard integer type (). Python handles large integers automatically anyway.
Intuition
If we were to try every possible path using Depth-First Search (DFS), how many paths would there be? From to taking only Right and Down steps requires exactly moves total. The number of unique permutations is roughly , which grows exponentially with grid size (). For a grid, this would be millions of paths—too slow for an interview setting (Time Limit Exceeded risk).
The Key Insight:
This problem exhibits Optimal Substructure. To reach cell (i, j) with the minimum cost, we must have arrived from either directly above (i-1, j) or to the left (i, j-1). The decision at any point depends only on the best path found so far for those neighbors. This means if we know the min-cost paths to all previous cells in a row/column, we can compute the current cell’s cost without re-exploring past states.
This suggests Dynamic Programming (DP). We build up the solution by filling out costs for each cell based on previously computed values. Since we only need data from the immediate top and left neighbors, this is an iterative DP approach rather than recursion with memoization to avoid stack overhead.
Approach
- State Definition: Let
dp[i][j]represent the minimum path sum required to reach cell(i, j)starting from(0, 0). - Initialization: We can create a DP table of size . To avoid complex boundary checks inside loops (like checking if row/col is
> 0), we will handle the first row and column logic explicitly or use padding. For clarity in this walkthrough, I’ll iterate through rows and columns with explicit conditionals for boundaries to keep memory usage strictly without extra overhead of a padded grid (though space optimization to is possible). - Base Case: The starting cell
dp[0][0]equalsgrid[0][0]. - Transitions: For any other cell
(i, j):- If it’s in the first row (
i == 0), we can only come from the left:dp[i][j] = dp[i][j-1] + grid[i][j]. - If it’s in the first column (
j == 0), we can only come from above:dp[i][j] = dp[i-1][j] + grid[i][j]. - Otherwise, take the minimum of coming from top or left:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j].
- If it’s in the first row (
- Result: The value at
dp[m-1][n-1]is our answer.
Complexity Analysis
- Time Complexity: . We visit each cell in the grid exactly once to compute its DP state. With constraints up to , this results in roughly 40,000 operations, which is negligible for modern hardware (well under typical time limits).
- Space Complexity: for the
dptable storing intermediate sums. This can be optimized to using a rolling array approach where we only store one row at a time, but given constraints and readability requirements in an interview context, allocating a full grid is acceptable unless memory limits are tight (e.g., embedded systems).
Solution
class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
m = len(grid)
n = len(grid[0])
# Initialize DP table with same dimensions as input.
# We can modify this in-place to save space, but creating a new one avoids side effects.
dp = [[0] * n for _ in range(m)]
# Base case: starting point cost is the value at (0, 0)
dp[0][0] = grid[0][0]
# Fill first row: can only come from left neighbor
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# Fill first column: can only come from top neighbor
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Iterate through the rest of the grid
for i in range(1, m):
for j in range(1, n):
# Minimum path sum is current cell value plus min cost from top or left
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
# Example usage:
grid_example = [[1,3,1],[1,5,1],[4,2,1]]
print(minPathSum(grid_example)) # Output: 7
Edge Cases Handled
- Single Cell Grid: The loops for filling rows/cols won’t execute (ranges are empty),
dp[0][0]is set correctly, and the function returns that single value. Correctly handles . - Empty Input: Added a check at the start (
if not grid...) to return 0 or handle gracefully if input validation isn’t guaranteed by caller (though constraints saym,n >= 1). - Single Row/Column: The nested loops skip boundary checks for first row/column, relying on separate initialization loops. This ensures correct accumulation along the single valid path without index errors.