Skip to main content

54. Minimum Path Sum

mediumAsked at Reddit

Find the path from top-left to bottom-right with minimum sum (right/down only). Reddit uses this to extend grid DP with weights — the same routing pattern they'd use to minimize CDN-cost for inter-region replication.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit data-platform phone screen, DP medium.

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: 1 -> 3 -> 1 -> 1 -> 1 = 7.

Example 2

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

Approaches

1. Recursion with memo

min(i, j) = grid[i][j] + min(min(i-1,j), min(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 dfs(i, j) {
    if (i === 0 && j === 0) return grid[0][0];
    if (i < 0 || j < 0) return Infinity;
    if (memo[i][j] !== -1) return memo[i][j];
    return memo[i][j] = grid[i][j] + Math.min(dfs(i - 1, j), dfs(i, j - 1));
  }
  return dfs(m - 1, n - 1);
}

Tradeoff: Recursion stack depth = m+n.

2. Iterative DP, in-place (optimal)

Overwrite grid: grid[i][j] += min(grid[i-1][j], grid[i][j-1]). Bottom-right cell is the answer.

Time
O(m*n)
Space
O(1) extra
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: Mutates input. If forbidden, use O(n) rolling array.

Reddit-specific tips

Reddit interviewers grade on whether you ask about input mutation. Bonus signal: discuss the 1D rolling memory trick and connect to cost-minimization routing in CDN replication graphs.

Common mistakes

  • Forgetting the i=0 or j=0 boundary cases (no predecessor on one side).
  • Allocating a new 2D matrix when in-place works.
  • Treating it as unweighted (Unique Paths) and missing the sum.

Follow-up questions

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

  • Minimum Path Sum with diagonals.
  • Maximum path sum.
  • Dungeon game (LC 174) — same shape, backwards DP.

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 the in-place mutation safe?

We only read each cell's value once before overwriting it; dependencies (left and up) are already updated.

Could BFS work?

BFS finds shortest by hop count, not by sum. You'd need Dijkstra for weighted, which is overkill for monotone grids.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →