Skip to main content

64. Minimum Path Sum

medium

Find a path from the top-left to the bottom-right of an m x n grid that minimizes the sum of values, moving only right or down. The min-cost twin of Unique Paths — same recurrence shape, swap addition for taking the minimum.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

Constraints

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

Examples

Example 1

Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7

Explanation: Because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2

Input
grid = [[1,2,3],[4,5,6]]
Output
12

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Same DAG shape as Unique Paths. Each cell can be reached from above or from the left.

Hint 2

Cost to reach (i, j) = grid[i][j] + min(cost(i-1, j), cost(i, j-1)).

Hint 3

First row only inherits from the left; first column only inherits from above. Space can be optimized to a single 1D row.

Solution approach

Reveal approach

Bottom-up DP. dp[i][j] is the minimum sum to reach (i, j). Initialize dp[0][0] = grid[0][0]. Fill the first row left to right (each cell adds the cell to its left) and the first column top to bottom. For every inner cell, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Return dp[m-1][n-1]. Space optimization: process row by row and keep a single 1D array of length n — dp[j] = grid[i][j] + min(dp[j] (which is the value from the previous row), dp[j-1] (just-updated cell to the left)).

Complexity

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

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Goldman Sachs
  • Microsoft

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →