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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Minimum Path Sum and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →