Minimum Path Sum

Difficulty: Medium Source: NeetCode

Problem

Given an m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right which minimizes the sum of all numbers along the path. You can only move right or down.

Example 1: Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: The path 1 → 3 → 1 → 1 → 1 has sum 7.

Example 2: Input: grid = [[1,2,3],[4,5,6]] Output: 12

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Unique Paths (62) — same grid traversal pattern
• 2D DP — understanding how cell values depend on neighbours

1. Brute Force / Recursive

Intuition

At every cell, choose the cheaper option — coming from above or from the left. Recurse from the destination back to the source. The base case is the top-left cell, which costs exactly grid[0][0]. Since all values are non-negative, we never need to explore all paths — we just take the minimum at each step, though without memoization we’ll redo the same subproblems repeatedly.

Algorithm

1. Define dfs(i, j) returning the minimum cost path to reach (i, j).
2. If i == 0 and j == 0, return grid[0][0].
3. If i == 0, return grid[0][j] + dfs(0, j-1) (can only come from left).
4. If j == 0, return grid[i][0] + dfs(i-1, 0) (can only come from above).
5. Otherwise return grid[i][j] + min(dfs(i-1, j), dfs(i, j-1)).

Solution

def minPathSum(grid):
    def dfs(i, j):
        if i == 0 and j == 0:
            return grid[0][0]
        if i == 0:
            return grid[0][j] + dfs(0, j - 1)
        if j == 0:
            return grid[i][0] + dfs(i - 1, 0)
        return grid[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))

    m, n = len(grid), len(grid[0])
    return dfs(m - 1, n - 1)


print(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7
print(minPathSum([[1, 2, 3], [4, 5, 6]]))              # 12

Complexity

• Time: O(2^(m+n)) — exponential overlap without memoization
• Space: O(m+n) — recursion stack

2. Bottom-Up DP (Tabulation)

Intuition

Build a dp table where dp[i][j] stores the minimum cost to reach cell (i, j). The first row can only be reached by going right, and the first column can only be reached by going down, so those are straightforward prefix sums. Every other cell is grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The answer is in the bottom-right corner.

Algorithm

1. Create a m x n dp table.
2. dp[0][0] = grid[0][0].
3. Fill first row: dp[0][j] = dp[0][j-1] + grid[0][j].
4. Fill first column: dp[i][0] = dp[i-1][0] + grid[i][0].
5. For interior: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
6. Return dp[m-1][n-1].

Solution

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    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])

    return dp[m - 1][n - 1]


print(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7
print(minPathSum([[1, 2, 3], [4, 5, 6]]))              # 12
print(minPathSum([[1]]))                                # 1

Complexity

• Time: O(m * n)
• Space: O(m * n) — can be optimised to O(n) by reusing a single row

Common Pitfalls

Using min on the entire row/column. The minimum path isn’t the cell with the smallest individual value — you need the minimum cumulative cost. Always add grid[i][j] to dp[i][j], not just carry the smaller neighbour.

Forgetting to seed the edges. If you initialise everything to 0 and only fill interior cells, the edge cells will have wrong values because they can only be reached from one direction.

In-place modification confusion. You can modify grid in place (skipping the dp array) — just make sure you understand what grid[i][j] means after you’ve overwritten it.