What is the Minimum Path Sum Problem?
Learn the minimum path sum grid DP problem, its recurrence, complexity, and how to answer this interview question with confidence.
Expected Interview Answer
The minimum path sum problem asks for the smallest total cost of a path from the top-left to the bottom-right of a grid, moving only right or down, and it is solved in O(rows * cols) time with dynamic programming by building each cell from the cheaper of its top or left neighbor.
Define dp[i][j] as the minimum cost to reach cell (i, j) from the start. The recurrence is dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), with the first row and first column each filled by a running sum since they only have one possible incoming direction. The answer ends up in dp[rows-1][cols-1], the bottom-right cell. Because each dp[i][j] only depends on the row above and the current row, the grid can be compressed to a single 1D array, dropping space from O(rows * cols) to O(cols).
- O(rows * cols) time, visits every cell once
- O(cols) space with a rolling 1D array
- Reuses overlapping subproblems instead of exploring every path
- Generalizes to obstacle grids and unique-path counting variants
AI Mentor Explanation
A ground staff crew maps every possible route a water truck can take from one corner of the outfield to the opposite corner, only ever allowed to move toward the boundary or toward the far sightscreen, never backward. Each patch of grass has its own watering cost, and the crew wants the cheapest total route. Instead of trying every path, they record the cheapest cost to reach each patch by adding that patch cost to whichever neighbor above or to its left was already cheaper to reach. By the time the truck plan reaches the far corner, the cheapest total has been built up patch by patch, never recomputing a route twice.
Step-by-Step Explanation
Step 1
Define the state
dp[i][j] holds the minimum cost to reach cell (i, j) from the top-left, moving only right or down.
Step 2
Fill the base row and column
The first row and first column are running sums since each has only one possible incoming direction.
Step 3
Apply the recurrence
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) for every other cell.
Step 4
Read the answer, optimize space
dp[rows-1][cols-1] is the result; a rolling 1D array reduces space to O(cols).
What Interviewer Expects
- Correctly state the recurrence and both base cases
- Explain why only right/down movement makes this a DP grid problem, not a graph search
- Give the O(rows * cols) time complexity
- Mention the O(cols) space optimization using a 1D rolling array
Common Mistakes
- Forgetting to initialize the first row and column as running sums
- Using recursion without memoization, causing exponential blowup
- Allowing movement in all four directions instead of only right/down
- Off-by-one errors when indexing the last cell for the final answer
Best Answer (HR Friendly)
“The minimum path sum problem is about finding the cheapest way to walk across a grid from one corner to the other, only moving right or down. I solve it by building up the cheapest cost to reach every cell from the cheapest cost to reach its neighbors, so I never have to check every possible route by brute force.”
Code Example
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [0] * cols
dp[0] = grid[0][0]
for j in range(1, cols):
dp[j] = dp[j - 1] + grid[0][j]
for i in range(1, rows):
dp[0] += grid[i][0]
for j in range(1, cols):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
return dp[cols - 1]Follow-up Questions
- How would you also reconstruct the actual path, not just the minimum sum?
- How does this change if diagonal movement is also allowed?
- How would you handle a grid with blocked or invalid cells?
- How would you solve this if the grid was too large to fit in memory?
MCQ Practice
1. What is the time complexity of the standard DP solution to minimum path sum on an m x n grid?
Each of the m * n cells is computed once in constant time, giving O(m * n) overall.
2. What is the space-optimized complexity of this DP using a rolling 1D array?
Only the previous row is needed at any time, so a single array of length n (columns) suffices.
3. Why are the first row and first column filled with running sums before the main loop?
Cells in the first row can only be reached from the left, and cells in the first column only from above.
Flash Cards
What is the recurrence for minimum path sum? — dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
What is the time complexity for an m x n grid? — O(m * n), since every cell is visited exactly once.
How can space be optimized from O(m*n) to O(n)? — Use a single 1D rolling array since each row only depends on the row above it.
Where is the final answer stored in the DP table? — In the bottom-right cell, dp[rows-1][cols-1].