Skip to main content

54. Minimum Path Sum

mediumAsked at Ola

Find the minimum-cost top-left-to-bottom-right path in a grid.

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

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 down or right at any point.

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

Recurse from origin; min of right and down at each cell.

Time
O(2^(m+n))
Space
O(m+n)
const f = (r,c) => r===m-1 && c===n-1 ? grid[r][c] : grid[r][c] + Math.min(r+1<m?f(r+1,c):Infinity, c+1<n?f(r,c+1):Infinity);
return f(0,0);

Tradeoff:

2. In-place DP

Overwrite grid[i][j] = grid[i][j] + min(top, left). Final cell is the answer.

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

Tradeoff:

Ola-specific tips

Ola interviewers like the in-place DP overwrite; tie it to selecting the lowest-toll route between two zones on a precomputed cost grid.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →