Skip to main content

52. Minimum Path Sum

mediumAsked at Workday

Find the minimum-sum path from top-left to bottom-right of a grid moving only right or down. Workday uses this for DP-on-grids fluency — same shape as finding the lowest-cost approval chain through a multi-tier authorization graph.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone 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 without memo

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

Time
O(2^(m+n))
Space
O(m+n)
function f(i,j){ if(i===0&&j===0) return grid[0][0]; ... }

Tradeoff: Exponential.

2. In-place DP

Mutate the grid: each cell becomes its own value plus the min of the cell above and left.

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: O(1) extra space by mutating the grid. If you can't mutate, use O(n) rolling row.

Workday-specific tips

Workday grades whether you ask 'can I mutate the input?' before coding. If yes, in-place wins. If not, a 1D rolling row is O(n) space. Walk through the boundary conditions (first row, first column) explicitly.

Common mistakes

  • Forgetting to handle the first row/column specially — they have only one predecessor.
  • Initializing dp[0][0] to 0 instead of grid[0][0].
  • Updating cells in the wrong order (must be top-to-bottom, left-to-right).

Follow-up questions

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

  • Triangle (LC 120).
  • Dungeon Game (LC 174) — backward DP.
  • Cherry Pickup (LC 741).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Mutate input?

Ask the interviewer. If allowed, in-place is O(1) extra. If not, a 1D rolling row is the next-best.

Can negative weights exist?

Prompt says non-negative. With negatives, Dijkstra-like shortest path is needed since DP-on-grid assumes monotone increase along any direction.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →