Minimum Path Sum
Asked at Goldman Sachs
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
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.
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]).
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.
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.
Visual walkthrough for [[1,3,1],[1,5,1],[4,2,1]]:
row 0: dp = [1, 4, 5]
row 1: dp[0]=1+1=2, dp[1]=5+min(4,2)=7, dp[2]=1+min(5,7)=6 -> [2,7,6]
row 2: dp[0]=2+4=6, dp[1]=2+min(7,6)=8, dp[2]=1+min(6,8)=7 -> [6,8,7]
answer = 7
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).
What Trips People Up in Real Interviews
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.
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.