Skip to main content

52. Minimum Path Sum

mediumAsked at Vercel

Find the minimum sum path from top-left to bottom-right in a grid, moving only right or down. Vercel asks this for the weighted-grid DP variation — same recurrence as cheapest-route in their multi-region edge deployment cost matrix.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel screen; in-place DP expected.
  • Blind (2026-Q1)— Listed in Vercel platform engineer screen.

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 top-down with memo

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

Time
O(m*n)
Space
O(m*n)
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const memo = Array.from({length: m}, () => new Array(n).fill(-1));
  function go(i, j) {
    if (i === m - 1 && j === n - 1) return grid[i][j];
    if (i === m || j === n) return Infinity;
    if (memo[i][j] !== -1) return memo[i][j];
    return memo[i][j] = grid[i][j] + Math.min(go(i + 1, j), go(i, j + 1));
  }
  return go(0, 0);
}

Tradeoff: O(mn) but uses stack. Iterative DP is preferred.

2. In-place DP (optimal)

Modify grid in place. First row: cumulative sum from left. First column: cumulative sum from top. Each other cell: grid[i][j] += min(top, left).

Time
O(m*n)
Space
O(1) extra (mutates input)
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      if (i === 0) grid[i][j] += grid[i][j - 1];
      else if (j === 0) grid[i][j] += grid[i - 1][j];
      else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }
  return grid[m - 1][n - 1];
}

Tradeoff: O(1) extra space by mutating the input. If mutation isn't allowed, use a separate dp array of the same shape or roll to O(n) space.

Vercel-specific tips

Vercel grades the in-place DP. Bonus signal: asking whether mutating the input is allowed (always ask) and offering the rolling-row alternative if not. The first-row/first-column initialization is the most common bug area — articulate it explicitly.

Common mistakes

  • Forgetting to initialize first row/column via cumulative sum — produces garbage on boundaries.
  • Using Math.min on grid[i-1][j] when i == 0 — accesses grid[-1][j] = undefined.
  • Mutating the input without permission — clarify first.

Follow-up questions

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

  • Unique Paths (LC 62) — count instead of sum.
  • Minimum Path Sum with obstacles.
  • Triangle (LC 120) — DP on a non-rectangular grid.

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 mutate in place?

Saves the O(mn) dp array. If the caller doesn't need the original grid, mutating it is fine; otherwise use a separate dp.

Can I do this in O(n) space?

Yes — keep only the current row, update left-to-right using the previous row's value (which is at dp[j] before update). Same rolling-row trick as Unique Paths.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →