Domain 2MediumCORE

Minimum Path Sum

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Dynamic Programming

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 m,nm, n are between 1 and 200. Values are ≥0\ge 0.
  • Outputs: An integer representing the minimum path sum.

Implicit Edge Cases to Consider:

  • Single cell grid (1×11 \times 1): 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 200×200200 \times 200, the maximum possible sum fits comfortably within a standard integer type (40,00040,000). 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 (0,0)(0,0) to (m,n)(m,n) taking only Right and Down steps requires exactly n+m−2n + m - 2 moves total. The number of unique permutations is roughly (m+nm)\binom{m+n}{m}, which grows exponentially with grid size (O(2m+n)O(2^{m+n})). For a 10×1010 \times 10 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

  1. State Definition: Let dp[i][j] represent the minimum path sum required to reach cell (i, j) starting from (0, 0).
  2. Initialization: We can create a DP table of size m×nm \times n. 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 O(m×n)O(m \times n) without extra overhead of a padded grid (though space optimization to O(n)O(n) is possible).
  3. Base Case: The starting cell dp[0][0] equals grid[0][0].
  4. 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].
  5. Result: The value at dp[m-1][n-1] is our answer.

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n). We visit each cell in the grid exactly once to compute its DP state. With constraints up to 200×200200 \times 200, this results in roughly 40,000 operations, which is negligible for modern hardware (well under typical time limits).
  • Space Complexity: O(m×n)O(m \times n) for the dp table storing intermediate sums. This can be optimized to O(n)O(n) 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 m=1,n=1m=1, n=1.
  • 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 say m,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.