Skip to main content

53. Minimum Path Sum

mediumAsked at Salesforce

Find the path from top-left to bottom-right of a grid with minimum sum. Salesforce uses this to test 2D DP with grid traversal.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses grid-DP in their routing optimization for field service.
  • LeetCode Discuss (2025)— Common pairing with Unique Paths.

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. 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 with memo

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

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 dp(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(dp(i - 1, j), dp(i, j - 1));
  }
  return dp(m - 1, n - 1);
}

Tradeoff: Clear DP statement but O(m*n) memo + recursion stack.

2. Iterative DP with in-place updates

Update grid in place: grid[i][j] += min(grid[i-1][j], grid[i][j-1]).

Time
O(m*n)
Space
O(1) if input mutation OK
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;
    const fromTop = i > 0 ? grid[i - 1][j] : Infinity;
    const fromLeft = j > 0 ? grid[i][j - 1] : Infinity;
    grid[i][j] += Math.min(fromTop, fromLeft);
  }
  return grid[m - 1][n - 1];
}

Tradeoff: O(1) extra space by mutating input. If input mutation is disallowed, use a O(n) rolling row.

Salesforce-specific tips

Salesforce explicitly tests whether you can compress to O(1) or O(min(m,n)) extra space. Bonus signal: walk through what changes for Unique Paths II (LC 63, with obstacles) — same DP, but obstacle cells get value Infinity.

Common mistakes

  • Using -1 sentinel for impossible states — fine but Infinity is cleaner for min DPs.
  • Off-by-one when i or j is 0 — must default the missing direction to Infinity.
  • Not handling the (0, 0) cell — its cost is grid[0][0], not 2 * grid[0][0].

Follow-up questions

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

  • Unique Paths II (LC 63) — with obstacles.
  • Minimum Falling Path Sum (LC 931) — same idea, different geometry.
  • Dungeon Game (LC 174) — 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 use Infinity for out-of-bounds?

Because the path can't enter out-of-bounds; treating it as Infinity ensures min picks the valid direction every time.

What about O(n) space?

Keep one row of length n. Update in place left-to-right. Each cell becomes the min path sum to reach it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →