64. Minimum Path Sum - Explanation

Problem Link

Description

You are given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [
    [1,2,0],
    [5,4,2],
    [1,1,3]
]

Output: 8

Explanation: The path with minimum sum is 1 -> 2 -> 0 -> 2 -> 3.

Example 2:

Input: grid = [
    [2,2],
    [1,0]
]

Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

Intuition

From any cell, we can only move right or down. To find the minimum path sum to the bottom-right corner, we consider both choices and take the minimum. At the destination cell, we simply return its value. This naturally leads to a recursive solution where we explore all possible paths by branching at each cell.

Algorithm

  1. Define a recursive function dfs(r, c) that returns the minimum path sum from cell (r, c) to the bottom-right.
  2. Base case: if we reach the bottom-right cell, return grid[r][c].
  3. If we go out of bounds (past the last row or column), return infinity to indicate an invalid path.
  4. For each cell, return grid[r][c] + min(dfs(r+1, c), dfs(r, c+1)).
  5. Start the recursion from dfs(0, 0).
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        def dfs(r, c):
            if r == len(grid) - 1 and c == len(grid[0]) - 1:
                return grid[r][c]
            if r == len(grid) or c == len(grid[0]):
                return float('inf')
            return grid[r][c] + min(dfs(r + 1, c), dfs(r, c + 1))

        return dfs(0, 0)

Time & Space Complexity

  • Time complexity: O(2m+n)O(2 ^ {m + n})
  • Space complexity: O(m+n)O(m + n) for recursion stack.

Where mm is the number of rows and nn is the number of columns.

2. Dynamic Programming (Top-Down)

Intuition

The plain recursive solution recalculates the same cells many times. For instance, both dfs(0,1) and dfs(1,0) might call dfs(1,1). By caching (memoizing) results for each cell, we ensure each subproblem is solved only once. This transforms exponential time into polynomial time.

Algorithm

  1. Create a 2D memoization table dp initialized to -1 (indicating uncomputed).
  2. Define dfs(r, c) as before, but first check if dp[r][c] has been computed.
  3. If dp[r][c] != -1, return the cached value.
  4. Otherwise, compute dp[r][c] = grid[r][c] + min(dfs(r+1, c), dfs(r, c+1)) and return it.
  5. Return dfs(0, 0).
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[-1] * n for _ in range(m)]

        def dfs(r, c):
            if r == m - 1 and c == n - 1:
                return grid[r][c]
            if r == m or c == n:
                return float('inf')
            if dp[r][c] != -1:
                return dp[r][c]

            dp[r][c] = grid[r][c] + min(dfs(r + 1, c), dfs(r, c + 1))
            return dp[r][c]

        return dfs(0, 0)

Time & Space Complexity

  • Time complexity: O(m∗n)O(m * n)
  • Space complexity: O(m∗n)O(m * n)

Where mm is the number of rows and nn is the number of columns.

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursing from top-left to bottom-right, we can fill a DP table starting from the bottom-right corner. For each cell, we know the minimum path sum to reach the destination from the cell below and from the cell to the right. We take the minimum of these two and add the current cell value. This iterative approach avoids recursion overhead.

Algorithm

  1. Create a DP table of size (ROWS+1) x (COLS+1) initialized to infinity. The extra row and column handle boundary conditions.
  2. Set dp[ROWS-1][COLS] = 0 as the base case (one position past the destination, allowing the destination cell to be computed correctly).
  3. Iterate from bottom-right to top-left: for each cell (r, c), set dp[r][c] = grid[r][c] + min(dp[r+1][c], dp[r][c+1]).
  4. Return dp[0][0].
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dp = [[float("inf")] * (COLS + 1) for _ in range(ROWS + 1)]
        dp[ROWS - 1][COLS] = 0

        for r in range(ROWS - 1, -1, -1):
            for c in range(COLS - 1, -1, -1):
                dp[r][c] = grid[r][c] + min(dp[r + 1][c], dp[r][c + 1])

        return dp[0][0]

Time & Space Complexity

  • Time complexity: O(m∗n)O(m * n)
  • Space complexity: O(m∗n)O(m * n)

Where mm is the number of rows and nn is the number of columns.

4. Dynamic Programming (Space Optimized)

Intuition

When filling the DP table row by row (from bottom to top), we only need the current row and the row below. In fact, since we process columns right to left, we can overwrite the same 1D array. The value at dp[c] represents the minimum path sum from (r+1, c), and dp[c+1] represents the path from (r, c+1). After updating, dp[c] will hold the result for (r, c).

Algorithm

  1. Create a 1D array dp of size COLS+1 initialized to infinity.
  2. Set dp[COLS-1] = 0 as the base case.
  3. For each row from bottom to top:
    • For each column from right to left: dp[c] = grid[r][c] + min(dp[c], dp[c+1]).
  4. Return dp[0].
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dp = [float("inf")] * (COLS + 1)
        dp[COLS - 1] = 0

        for r in range(ROWS - 1, -1, -1):
            for c in range(COLS - 1, -1, -1):
                dp[c] = grid[r][c] + min(dp[c], dp[c + 1])

        return dp[0]

Time & Space Complexity

  • Time complexity: O(m∗n)O(m * n)
  • Space complexity: O(n)O(n)

Where mm is the number of rows and nn is the number of columns.