Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Let dp[i][j] be the cheapest path sum from the top-left to cell (i, j) moving only right or down. Then dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), with the first row and column as running prefix sums. Naive recursion is exponential; the DP is O(mn) time, O(mn) space, and compresses to a single O(n) rolling row.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that right/down-only movement forces a two-term recurrence (top or left), handle the first row/column base cases, and know to MIN over predecessors while ADDING the current cell.
Where candidates slip
Forgetting the first row/column are prefix sums (treating their missing neighbours as 0 cost), or summing the two predecessors instead of taking the min.
How to stand out
State the recurrence from 'a cell is reachable only from top or left', handle the borders explicitly, then compress to a single O(n) row updated in place.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCheapest right/down path top-left to bottom-rightBrute force every path?YesNoExplore the full treeCollapse the tree
How to read it:Right/down moves mean (i, j) has exactly two predecessors. Extend the cheaper one and add the current value.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recurse Both Moves
1Hint 1Explore hintHide hint
From any cell you can go right or down. The cheapest path from here to the goal is this cell's value plus the cheaper of those two continuations.
2Hint 2Explore hintHide hint
Write cost(i, j) = grid[i][j] + min(cost(i+1, j), cost(i, j+1)), recursing toward the bottom-right.
3Hint 3Explore hintHide hint
Base case: the destination cell returns its own value; stepping off the grid returns +infinity so it's never chosen.
A · Core idea
Translate the movement rules directly: from cell (i, j) you may step right to (i, j+1) or down to (i+1, j). The cheapest cost to finish from (i, j) is grid[i][j] plus the smaller of the two recursive continuations.
Why this is the honest first attempt. The problem is literally 'choose right or down at each step to minimize the total'. The recursion makes that choice explicit at every cell and lets min pick the better branch. No insight about reuse is needed yet — just exhaustive choice.
Why the base cases are what they are. At the bottom-right cell there's nothing left to do, so it returns its own value. Stepping past the last row or column is illegal; modeling that as +infinity guarantees min never selects an off-grid move, so we don't need special boundary branches sprinkled through the logic.
Why we don't ship this. Two length-200 sides give paths of ~400 moves and a recursion tree near 2^400 — utterly intractable. Crucially, the same cell (i, j) is reached by exponentially many different prefixes, and each time we recompute cost(i, j) from scratch. That overlap — identical subproblems revisited — is the unmistakable cue to memoize, then tabulate.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[1,3],[1,5]]Live grid state
Cells change as the traversal moves
cost(0,0)1 + min(cost(1,0), cost(0,1))
7C · Code with teaching comments
Reference implementation previewpublic int minPathSum(int[][] grid) { return cost(grid, 0, 0); } private int cost(int[][] grid, int i, int j) {Explore the full codeHide the full code
D · Why it works and complexityO(2^(m+n)) timeO(m + n) spaceOpen the invariant and proofExplore the proofHide the proof
Different prefixes converge on the same cell, and the cost from that cell onward doesn't depend on how you arrived — only on where you are. That 'future is independent of the past given the current state' property is exactly what lets caching collapse the exponential path count into one value per cell.
ComplexityO(2^(m+n)) time, O(m + n) space — Each call branches into two (right and down), and a path is m+n−2 moves long, so the recursion tree has up to ~2^(m+n) nodes. Stack depth is O(m+n).
E · Edge cases and pitfalls5grid = [[5]] — Start equals destination → the base case returns 5 immediately.Explore edge casesHide edge cases
Edge cases handled
grid = [[5]]Start equals destination → the base case returns 5 immediately.single row [[1,2,3]]Down is always off-grid (inf), so the path is forced right: 1+2+3 = 6.
Pitfalls
- Returning 0 for off-grid instead of +infinity — lets min pick an illegal move and undercounts.
- Summing the two continuations instead of taking the min — counts both branches.
- Shipping the recursion — exponential and hopeless for 200×200 grids.
Approach 2 of 3
Bottom-Up 2D DP — Cell + min(Top, Left)
1Hint 1Explore hintHide hint
Flip the direction: instead of cost-to-finish from a cell, compute cost-to-REACH each cell from the top-left. Then dp[m-1][n-1] is the answer.
2Hint 2Explore hintHide hint
A cell is entered only from above or from the left, so dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
3Hint 3Explore hintHide hint
Seed the borders: dp[0][0] = grid[0][0]; the first row and first column are running prefix sums since each has just one way in.
A · Core idea
Define dp[i][j] as the minimum sum of any right/down path from the start (0, 0) to cell (i, j). Because movement is monotone, (i, j) can only be entered from directly above or directly to the left, so its best cost is its own value plus the cheaper of those two predecessors.
Why the borders are prefix sums. The top-left cell has no predecessor, so dp[0][0] = grid[0][0]. Any cell in the first row can only be reached by moving right along that row — a single forced path — so dp[0][j] = dp[0][j-1] + grid[0][j]. Likewise the first column is reached only by moving down: dp[i][0] = dp[i-1][0] + grid[i][0]. Skipping these and pretending a missing neighbour costs 0 would let interior cells 'inherit' a free path that doesn't exist.
Why min, and why we still add the cell. This is an optimization, not a count: among the (at most two) ways to arrive, we keep the cheaper, hence min. But every path that ends at (i, j) must stand on (i, j), so its value is always added. Confusing this with Unique Paths — where you sum the two predecessors to count routes — is the classic trap.
Why a row-major fill is a valid order. Each dp[i][j] depends only on dp[i-1][j] (the row above, already done) and dp[i][j-1] (the same row, already done to the left). Scanning top-to-bottom, left-to-right therefore always has both dependencies ready. The answer is the bottom-right cell, dp[m-1][n-1].
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[1,3,1],[1,5,1],[4,2,1]]Live grid state
Cells change as the traversal moves
row 0prefix sums: 1, 1+3=4, 4+1=5
7C · Code with teaching comments
Reference implementation previewpublic int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for (int j = 1; j < n; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(mn) timeO(mn) spaceOpen the invariant and proofExplore the proofHide the proof
Reframing from 'cheapest cost to finish from here' (top-down) to 'cheapest cost to reach here' (bottom-up) is what removes the recursion: dependencies now point backward to already-filled cells, so a plain double loop suffices. That reframe — define the state as 'best value ending at this cell' — is the workhorse of nearly every grid DP.
ComplexityO(mn) time, O(mn) space — Every cell is filled once with O(1) work over an m×n grid → O(mn) time. The dp table stores one value per cell → O(mn) space.
E · Edge cases and pitfalls5grid = [[1,2,3]] — m = 1: only the first-row prefix-sum loop runs → dp = [1,3,6], answer 6.Explore edge casesHide edge cases
Edge cases handled
grid = [[1,2,3]]m = 1: only the first-row prefix-sum loop runs → dp = [1,3,6], answer 6.grid = [[1],[2],[3]]n = 1: only the first-column loop runs → dp = [1,3,6], answer 6.
Pitfalls
- Forgetting to seed the first row/column — interior cells then read uninitialized 0s and undercount.
- Summing dp[i-1][j] + dp[i][j-1] instead of taking the min — that counts paths (Unique Paths), not the cheapest cost.
- Returning dp[0][0] or a tracked min instead of dp[m-1][n-1] — the answer is specifically the destination cell.
Approach 3 of 3 · Optimal
Space-Optimized — Single Rolling Row (Optimal)
1Hint 1Explore hintHide hint
Look at the 2D recurrence: dp[i][j] reads dp[i-1][j] (the row above) and dp[i][j-1] (this row, already updated). Do you need all m rows in memory?
2Hint 2Explore hintHide hint
Keep one array of length n. Initialize it to the first row's prefix sums, then for each later row update it left to right in place.
3Hint 3Explore hintHide hint
When you reach index j, dp[j] still holds the value from the row above (the top), and dp[j-1] already holds this row's left — so dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
A · Core idea
The 2D recurrence never reaches further back than one row, so we can keep just one array dp of length n and overwrite it as we descend the grid. Before processing row i, dp holds row i-1; after the inner loop, it holds row i.
Why a single row is exact. When the inner loop reaches column j, two facts hold simultaneously: dp[j] has not yet been overwritten this row, so it still equals dp[i-1][j] — the value from directly above (the top). And dp[j-1] was just updated, so it equals dp[i][j-1] — this row's left neighbour. Those are precisely the two predecessors the full table reads. So dp[j] = grid[i][j] + min(dp[j], dp[j-1]) reproduces the 2D recurrence with no information lost.
Handling the borders in the rolled form. Initialize dp to the first row's prefix sums. For each subsequent row, the leftmost cell dp[0] has no left neighbour, so it just accumulates downward: dp[0] += grid[i][0]. Then the inner loop runs from j = 1. Unlike the saved-diagonal trick in Edit Distance or Maximal Square, this recurrence only needs the top and the left — never the diagonal — so no prev/temp stash is required, which makes it the simplest of the rolling-row DPs.
Why the left-to-right order is mandatory. We must read dp[j] as the top before overwriting it, and dp[j-1] must already be this row's value. Sweeping left to right satisfies both: each cell is updated exactly when its top is still stale and its left is already fresh. Reverse the direction and dp[j-1] would still be the old row, corrupting the recurrence.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[1,3,1],[1,5,1],[4,2,1]]Live grid state
Cells change as the traversal moves
init (row 0)prefix sums of [1,3,1]
7C · Code with teaching comments
D · Why it works and complexityO(mn) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
When a grid recurrence depends only on the row above and the cell immediately left, a single row updated left-to-right is all the memory you need — and because there's no diagonal term, this one needs no saved-corner scalar at all. Recognizing exactly which neighbours a recurrence touches tells you precisely how much state to keep.
ComplexityO(mn) time, O(n) space — Same O(mn) cell updates with O(1) work each. Storage is a single array of n values regardless of m → O(n) space.
E · Edge cases and pitfalls5single row — Only the init loop runs; dp ends as the row's prefix sums, returning the last entry.Explore edge casesHide edge cases
Edge cases handled
single rowOnly the init loop runs; dp ends as the row's prefix sums, returning the last entry.single columnn = 1, the inner loop never runs; dp[0] accumulates every row's value → the column total.
Pitfalls
- Iterating the inner loop right-to-left — dp[j-1] would still be the previous row, breaking the recurrence.
- Forgetting dp[0] += grid[i][0] each row — the first column loses its accumulated cost.
- Re-initializing dp inside the row loop — wipes out the row-above values you need as the 'top'.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0]; for (int j = 1; j < n; j++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Min vs sum of predecessors
Minimum Path Sum OPTIMIZES a cost, so you keep the cheaper predecessor. Summing them solves Unique Paths (counting routes) instead and returns a wildly inflated number.
Explore the code comparisonHide the code comparison
Min vs sum of predecessors
Minimum Path Sum OPTIMIZES a cost, so you keep the cheaper predecessor. Summing them solves Unique Paths (counting routes) instead and returns a wildly inflated number.
Don't write this
dp[i][j] = grid[i][j] + dp[i - 1][j] + dp[i][j - 1];Write this instead
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);2Unseeded borders
First-row and first-column cells have a single predecessor. Leaving them at 0 lets interior cells read a phantom free path from off the grid.
Explore the code comparisonHide the code comparison
Unseeded borders
First-row and first-column cells have a single predecessor. Leaving them at 0 lets interior cells read a phantom free path from off the grid.
Don't write this
dp = [[0] * n for _ in range(m)]
# jump straight to the interior double loopWrite this instead
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]3Wrong sweep direction in the rolled row
The O(n) version needs dp[j-1] to already hold the CURRENT row's left value. Iterating right-to-left leaves dp[j-1] as the previous row, silently producing wrong sums.
Explore the code comparisonHide the code comparison
Wrong sweep direction in the rolled row
The O(n) version needs dp[j-1] to already hold the CURRENT row's left value. Iterating right-to-left leaves dp[j-1] as the previous row, silently producing wrong sums.
Don't write this
for j in range(n - 1, 0, -1):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1])Write this instead
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1])Revise
Carry the pattern into the interview
Pattern to remember
2D grid DP — cheapest path, right/down only
Code pattern to memorize
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
first row: dp[0][j] = dp[0][j-1] + grid[0][j]
first col: dp[i][0] = dp[i-1][0] + grid[i][0]Rules to remember
- 1You may move only right or down, so a cell is reached only from its top or left neighbour — that's why the recurrence has exactly two terms.
- 2Always add the current cell's value
grid[i][j]; the choice is which cheaper predecessor to extend. - 3The first row and first column have only one way in (straight from the start), so they're plain prefix sums — get these base cases right or the interior is garbage.
- 4Take the min of the two predecessors (this is optimization), not the sum — a classic mix-up with counting DPs like Unique Paths.
- 5Each cell reads only the row above and the cell to its left, so the whole table collapses to one rolling row of length n → O(n) space.
Use this pattern when
- Cheapest / longest path through a grid with restricted moves (right/down)
- Each cell's optimum depends only on a couple of neighbouring cells
- Accumulating a cost while moving monotonically through a matrix
- Counting or optimizing over lattice paths
Choose another pattern when
- Moves in all four directions with arbitrary weights → Dijkstra / 0-1 BFS, not simple DP
- You need every path, not the best one → enumerate / backtrack
- Counting the number of paths, not their cost → Unique Paths (sum, not min)
- Negative cycles or revisiting cells allowed → shortest-path graph algorithms
Interview takeaway
Minimum Path Sum is the cleanest 'cheapest monotone path on a grid' DP: each cell is its own cost plus the cheaper of the two ways in. Once you see it, Unique Paths (count instead of min), Triangle, and Dungeon Game are the same grid recurrence with different operators and directions.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 'cheapest monotone path on a grid' DP. Recognize it whenever moves are restricted to right/down (or any monotone direction) and you optimize an accumulated cost. The same recurrence underpins Unique Paths (sum to count), Triangle, and — reversed — Dungeon Game.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Unique PathsSame grid, but COUNT paths instead of minimizing: dp[i][j] = dp[i-1][j] + dp[i][j-1].
- Unique Paths IIComing soonCounting variant with obstacles — blocked cells contribute 0 ways.
- TriangleSame cheapest-path idea on a triangular grid; bottom-up DP runs in O(n) space.
- Dungeon GameComing soonSame grid moves but DP runs bottom-right to top-left and tracks minimum health needed, not accumulated sum.