MediumArrayDynamic ProgrammingMatrixUpdated Sep 2026

64. Minimum Path Sum

Asked at Goldman Sachs

Difficulty

Medium

Time

O(m * n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a grid of non-negative numbers with m rows and n columns. You start at the top-left cell and want to reach the bottom-right cell.

On each step you may move only right or down. You cannot move left or up. The cost of a path is the sum of all numbers in the cells you visit, including the start cell and the end cell.

Return the smallest possible total cost over all valid paths.

Only right and down moves

grid012012131151421The marked path 1 → 3 → 1 → 1 → 1 costs 7, thecheapest possible
From the top-left corner you must reach the bottom-right corner using right and down steps only, paying the sum of every cell you touch.

Constraints

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

Examples

Example 1
Inputgrid = [[1,3,1],[1,5,1],[4,2,1]]
Output7
WhyThe cheapest route is 1 → 3 → 1 → 1 → 1, going right, right, down, down. Its sum is 7. Any other route costs more, for example 1 → 1 → 4 → 2 → 1 sums to 9.
Example 2
Inputgrid = [[1,2,3],[4,5,6]]
Output12
WhyWith only two rows you must go right twice and down once. The best order is 1 → 2 → 3 → 6, which sums to 12.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Brute force: recursively try going right and going down from every cell. That explores O(2^(m+n)) paths because the same cells are reached over and over.

2

Key insight: the cheapest way to reach cell (r, c) only depends on the cheapest way to reach the cell above it and the cell to its left. So dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).

3

The first row can only be reached from the left, and the first column only from above — fill those as running sums before the general recurrence.

4

Space optimization: you only ever look at the current row and the row above, so a single 1D array of width n is enough. dp[c] holds the value from the previous row until you overwrite it.

Optimal Approach

Step 1: Let dp be an array of length n.
Step 2: For each row r and column c:
If r == 0 and c == 0: dp[c] = grid[0][0].
Else if r == 0: dp[c] = dp[c-1] + grid[r][c] (only from the left).
Else if c == 0: dp[c] = dp[c] + grid[r][c] (only from above).
Else: dp[c] = grid[r][c] + min(dp[c], dp[c-1]).
Step 3: Return dp[n-1].

Each cell is computed once from two neighbors.

Time: O(m * n). Space: O(n).

Fill dp row by row

dp after row 00120145Row 0 has only one way in, from the left, so itbecomes a running sum: 1, 4, 5dp after row 10121276dp[1] = 5 + min(4, 2) = 7, taking the cheaper of thecell above and the cell to the leftdp after row 20122687The last cell gives 1 + min(6, 8) = 7, which is thefinal answerdp[c] = grid[r][c] + min(dp[c], dp[c-1])dp[c] before update = value from row abovedp[c-1] after update = value from the left
dp[c] holds the cheapest cost to reach the current row's column c, reusing the value from the row above until it is overwritten.
ComplexityTime O(m * n)Space O(n)Every cell is filled once from its top and left neighbors, and we keep only one row of values.

What Trips People Up in Real Interviews

1

Trying a greedy "always step to the cheaper neighbor". A cheap next step can lead into an expensive region; only DP compares full paths.

2

Forgetting the boundary rows. The first row and first column have only one possible predecessor — using min there reads out of bounds or a stale zero.

3

Using BFS or Dijkstra. It works, but it is heavier than needed. Because movement is only right/down, the grid is already a DAG in topological order, so DP is simpler and faster.

4

Not mentioning the O(n) space optimization. Interviewers usually ask for it as a follow-up once the 2D table version is correct.

Solution Code

O(m * n) time
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0:
                dp[c] = grid[0][0]
            elif r == 0:
                dp[c] = dp[c - 1] + grid[r][c]
            elif c == 0:
                dp[c] = dp[c] + grid[r][c]
            else:
                dp[c] = grid[r][c] + min(dp[c], dp[c - 1])
    return dp[n - 1]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Path Sum problem?

Minimum Path Sum gives you a grid of non-negative numbers and asks for the cheapest path from the top-left cell to the bottom-right cell, where you may only move right or down. It is a textbook 2D dynamic programming question and a common warm-up before harder grid DP problems.

How do you solve Minimum Path Sum?

The optimal approach runs in O(m * n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Path Sum?

Minimum Path Sum is asked at Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Minimum Path Sum?
  • Trying a greedy "always step to the cheaper neighbor". A cheap next step can lead into an expensive region; only DP compares full paths.
  • Forgetting the boundary rows. The first row and first column have only one possible predecessor — using `min` there reads out of bounds or a stale zero.
  • Using BFS or Dijkstra. It works, but it is heavier than needed. Because movement is only right/down, the grid is already a DAG in topological order, so DP is simpler and faster.
  • Not mentioning the `O(n)` space optimization. Interviewers usually ask for it as a follow-up once the 2D table version is correct.