Skip to main content

52. Minimum Path Sum

mediumAsked at Plaid

Find the path from top-left to bottom-right with the smallest sum. Plaid asks this as a grid DP variation, mapping cleanly to lowest-cost routing in their multi-hop payment-rail graph.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid grid DP.

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

Example 2

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

Approaches

1. Recursive

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

Time
O(2^(m+n))
Space
O(m+n)
// Exponential without memo. Mention as starting point.

Tradeoff: TLE without memo.

2. 1D DP in-place

Use the grid itself as the DP table. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Then collapse to one row.

Time
O(m*n)
Space
O(n) or O(1) if mutating grid
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: In-place: O(1) extra space. The first-row and first-column initializations are linear accumulations.

Plaid-specific tips

Plaid grades this on the in-place mutation trick when allowed. Bonus signal: ask whether mutating the input is OK before doing so. Discuss the rolling-row alternative when the input shouldn't be touched. Connect to lowest-cost routing across payment rails where each cell is a fee.

Common mistakes

  • Forgetting to handle the first row and first column separately — they don't have both neighbors.
  • Using > instead of < for the recurrence — finds max path instead of min.
  • Off-by-one in the final return — should be grid[m-1][n-1].

Follow-up questions

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

  • Allow moving up and left — turns it into Dijkstra.
  • Path itself, not just the sum.
  • Minimum path on a triangle (LC 120).

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 is in-place OK here?

We never re-read the original value of grid[i][j] after updating it — each cell is read by its neighbors before being updated.

What changes if we allow up/left moves?

The problem becomes shortest-path on a DAG, then on a graph with cycles if you also allow back-edges. Dijkstra (or 0-1 BFS) replaces the DP.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →