Skip to main content

52. Minimum Path Sum

mediumAsked at Datadog

Find the minimum-cost path from top-left to bottom-right of a grid, moving only right or down. Datadog uses this as a weighted-DP foundation before harder pathfinding questions.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — weighted DP variant.

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.

Example 2

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

Approaches

1. Recursive without memo

f(r, c) = grid[r][c] + min(f(r-1, c), f(r, c-1)).

Time
O(2^(m+n))
Space
O(m+n)
function minPathSum(grid) {
  function f(r, c) {
    if (r === 0 && c === 0) return grid[0][0];
    if (r < 0 || c < 0) return Infinity;
    return grid[r][c] + Math.min(f(r - 1, c), f(r, c - 1));
  }
  return f(grid.length - 1, grid[0].length - 1);
}

Tradeoff: Exponential without memo. Datadog will fail.

2. Bottom-up DP in place (optimal)

Mutate grid: grid[r][c] += min(grid[r-1][c], grid[r][c-1]). Handle first row and column specially.

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

Tradeoff: In-place mutation — O(1) extra space. If the input must not be mutated, use a rolling 1D array. Datadog accepts either.

Datadog-specific tips

Datadog will follow up with: 'Now reconstruct the actual path.' Show that you'd backtrack from (m-1, n-1): at each step, move to whichever predecessor had the smaller value. Streaming-friendly: emit path cells in reverse, then reverse.

Common mistakes

  • Forgetting the first-row and first-column special cases — accessing grid[-1][...] crashes.
  • Using Infinity as a sentinel in JS without checking — works but signals you're not careful with edge cases.
  • Computing the path-sum DP and then trying to reconstruct without saving direction — needs a separate pass.

Follow-up questions

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

  • Unique Paths (LC 62) — count paths instead of min.
  • Minimum Falling Path Sum (LC 931) — diagonal moves allowed.
  • Cherry Pickup (LC 741) — bidirectional pathfinding.

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 the grid?

It's O(1) extra space. If immutability matters, use a 1D rolling array — same time complexity, doesn't touch the input.

Can this be solved with Dijkstra?

Yes — treating cells as nodes with weighted edges. But on a grid with monotone moves, DP is O(m*n); Dijkstra is O(m*n log(m*n)). DP wins.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →