Skip to main content

54. Minimum Path Sum

mediumAsked at Snowflake

Find the minimum-sum path from top-left to bottom-right of a grid. Snowflake uses this to test 2D-DP with state compression — the same shape they apply when computing min-cost plans over an operator DAG.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to lead into plan-cost discussion.
  • LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

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: Path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2

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

Approaches

1. Recursive without memo

minSum(i, j) = grid[i][j] + min(minSum(i-1, j), minSum(i, j-1)).

Time
O(2^(m+n))
Space
O(m+n)
// outline only — exponential, don't ship.

Tradeoff: Exponential. Mention to reject.

2. 1D rolling DP (optimal)

dp[j] = min cost to reach column j in current row. dp[j] = grid[i][j] + min(dp[j] [from above], dp[j-1] [from left]).

Time
O(m * n)
Space
O(n)
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = new Array(n).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < m; i++) {
    dp[0] += grid[i][0];
    for (let j = 1; j < n; j++) {
      dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
    }
  }
  return dp[n - 1];
}

Tradeoff: Linear-state DP. The same shape as cost rollup in a plan DAG (each node = its own cost + min over inputs).

Snowflake-specific tips

Snowflake interviewers want the 1D rolling array and the explanation of why dp[j] before update is 'from above' while dp[j-1] is 'from left'. Bonus signal: connect to plan-cost rollup — Snowflake's planner computes min cost per plan node as cost(node) + min over child plans, exactly this recurrence on a DAG.

Common mistakes

  • Forgetting to seed dp[0] correctly — must accumulate first column's grid values.
  • Using max instead of min — usually a typo, but worth checking.
  • Initializing dp[j] to grid[0][j] inside the loop, overwriting accumulated state.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Minimum Path Sum with obstacles.
  • Maximum Path Sum (LC 124) — tree variant.
  • How does Snowflake compute plan cost?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why dp[0] += grid[i][0] inside the loop?

The first column has only one predecessor (the cell above). Accumulating grid[i][0] gives the correct cumulative cost down the left edge.

How does this map to plan cost?

Min path sum is a DP over a 2D grid. Plan cost is a DP over a DAG. Both follow: cost(node) = local cost + min over predecessor costs.

Practice these live with InterviewChamp.AI

Drill Minimum Path Sum and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →