Skip to main content

22. Minimum Path Sum

mediumAsked at Electronic Arts

Find the minimum cost path from top-left to bottom-right of a grid using DP, mirroring EA's movement cost and terrain-weight calculations in strategy game pathfinding.

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

Problem

Given an m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right corner 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

Example 2

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

Approaches

1. Recursive with memoization

Recurse from bottom-right, memoize subproblem results to avoid recomputation.

Time
O(m*n)
Space
O(m*n)
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const memo = {};
  function dp(r, c) {
    if (r === m-1 && c === n-1) return grid[r][c];
    if (r >= m || c >= n) return Infinity;
    const key = r+','+c;
    if (memo[key] !== undefined) return memo[key];
    memo[key] = grid[r][c] + Math.min(dp(r+1,c), dp(r,c+1));
    return memo[key];
  }
  return dp(0, 0);
}

Tradeoff:

2. Bottom-up DP in-place

Modify the grid in-place: each cell accumulates the minimum cost to reach it from top-left. No extra space needed, and EA interviewers appreciate the O(1) extra space technique for map-cost DP.

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

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

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 Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →