Minimum Path Sum

Minimum Path Sum

What is this problem about?

The Minimum Path Sum problem asks you to find the path from the top-left to the bottom-right corner of a grid that minimizes the sum of all cell values along the way. You can only move right or down at each step. Despite its simple statement, the Minimum Path Sum coding problem is a foundational dynamic programming exercise that underpins dozens of related grid DP problems seen in real interviews.

Why is this asked in interviews?

This is one of the most commonly asked questions by top-tier companies including Apple, Google, Microsoft, Amazon, Meta, Goldman Sachs, and Bloomberg. It cleanly tests bottom-up DP intuition and in-place optimization. Interviewers use it as a gateway problem — if a candidate stumbles on Minimum Path Sum, it signals gaps in DP fundamentals. The array, matrix, and dynamic programming interview pattern is perfectly embodied here.

Algorithmic pattern used

The approach is classic 2D dynamic programming. Define dp[i][j] as the minimum sum to reach cell (i, j). Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Base cases handle the first row (only left-to-right moves) and first column (only top-to-bottom moves). Space can be optimized to O(n) by using a 1D DP array, updating it as you scan each row.

Example explanation

Grid:

1  3  1
1  5  1
4  2  1

DP fills in:

• Row 0: [1, 4, 5]
• Row 1: [2, 7, 6]
• Row 2: [6, 8, 7]

The minimum path sum is 7, following the path: 1→3→1→1→1.

Common mistakes candidates make

• Forgetting to initialize the first row and first column separately before filling the rest.
• Modifying the original grid when the problem expects it unchanged.
• Attempting top-down memoization without proper base case handling.
• Off-by-one errors in 1D space-optimized versions.

Interview preparation tip

Minimum Path Sum is your entry point into grid DP. Master the 2D DP transition, then practice the O(n) space optimization. Once comfortable, extend your skills to problems with obstacles, multiple starting points, or diagonal moves. Being able to derive the recurrence on a whiteboard without hesitation is a hallmark of strong DP fundamentals — the exact signal interviewers look for.