Minimum Path Cost in a Grid

Medium
1630.

Minimum Path Cost in a Grid

Minimum Path Cost in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.

You are given an m x n grid grid holding each of the numbers 0 to m * n - 1 exactly once. From any cell (x, y) with x < m - 1 you may move to any cell of the next row, (x + 1, 0) through (x + 1, n - 1). Cells in the last row have no moves.

A move has a price: moving from a cell holding value v into column j of the next row costs moveCost[v][j].

A path starts at any cell of the first row and ends at any cell of the last row. Its cost is the sum of the values of all cells it visits plus the prices of all its moves. Return the minimum cost of a path.

Example 1

Input
grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Output
17
Explanation
Path 5 → 0 → 1: cell values 5 + 0 + 1 = 6, moves moveCost[5][1] = 3 and moveCost[0][1] = 8, total 17.

Example 2

Input
grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
Output
6
Explanation
Path 2 → 3: values 2 + 3 and move moveCost[2][2] = 1.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • grid is a permutation of 0..m*n-1
  • moveCost.length == m * n
  • moveCost[i].length == n
  • 1 <= moveCost[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number[][]} moveCost
 * @return {number}
 */
var minPathCost = function(grid, moveCost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Path Cost in a Grid — Solution in Python, Java & C++

Minimum Path Cost in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Path Cost in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Matrix
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an m x n grid grid holding each of the numbers 0 to m * n - 1 exactly once. From any cell (x, y) with x < m - 1 you may move to any cell of the next row, (x + 1, 0) through (x + 1, n - 1). Cells in the last row have no moves.

A move has a price: moving from a cell holding value v into column j of the next row costs moveCost[v][j].

A path starts at any cell of the first row and ends at any cell of the last row. Its cost is the sum of the values of all cells it visits plus the prices of all its moves. Return the minimum cost of a path.

Example 1

Input: grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Output: 17
Explanation: Path 5 → 0 → 1: cell values 5 + 0 + 1 = 6, moves moveCost[5][1] = 3 and moveCost[0][1] = 8, total 17.

Example 2

Input: grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
Output: 6
Explanation: Path 2 → 3: values 2 + 3 and move moveCost[2][2] = 1.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • grid is a permutation of 0..m*n-1
  • moveCost.length == m * n
  • moveCost[i].length == n
  • 1 <= moveCost[i][j] <= 100

Hints for Minimum Path Cost in a Grid

  1. Hint 1

    The cost of reaching a cell only depends on which cell of the previous row you came from — a row-by-row DP.

  2. Hint 2

    Let dp[j] be the cheapest cost of a path ending at column j of the current row (including that cell's value).

  3. Hint 3

    For the next row: new[j] = grid[r+1][j] + min over k of (dp[k] + moveCost[grid[r][k]][j]). The answer is the minimum of the last row.

How to solve Minimum Path Cost in a Grid

Each row only depends on the row above, so a DP over rows with one value per column finds the cheapest path in O(m * n^2).

Approach

  1. Start with dp[j] = grid[0][j] for the first row.
  2. For each next row r, compute new[j] = grid[r][j] + min over k of (dp[k] + moveCost[grid[r-1][k]][j]).
  3. Replace dp with new and continue.
  4. Return the minimum of dp after the last row.

Why it works

Any path to cell (r, j) arrives from some (r - 1, k), and its cost is the cost of the path to (r - 1, k) plus the move price and the new cell's value. Taking the cheapest path to every (r - 1, k) and minimising over k is therefore exact — the classic optimal-substructure argument.

Complexity

  • Time — O(m * n^2)
  • Space — O(n)

Pitfalls

  • The move price is indexed by the value in the cell you leave, not by its coordinates.
  • The path cost includes the values of the first and the last cell.

Reference solution

Python

from typing import List

def minPathCost(grid: List[List[int]], moveCost: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = grid[0][:]
    for r in range(1, m):
        nd = []
        for j in range(n):
            best = min(dp[k] + moveCost[grid[r - 1][k]][j] for k in range(n))
            nd.append(best + grid[r][j])
        dp = nd
    return min(dp)

Java

public static int minPathCost(int[][] grid, int[][] moveCost) {
    int m = grid.length, n = grid[0].length;
    int[] dp = grid[0].clone();
    for (int r = 1; r < m; r++) {
        int[] nd = new int[n];
        for (int j = 0; j < n; j++) {
            int best = Integer.MAX_VALUE;
            for (int k = 0; k < n; k++) best = Math.min(best, dp[k] + moveCost[grid[r - 1][k]][j]);
            nd[j] = best + grid[r][j];
        }
        dp = nd;
    }
    int ans = Integer.MAX_VALUE;
    for (int v : dp) ans = Math.min(ans, v);
    return ans;
}

C++

int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp = grid[0];
    for (int r = 1; r < m; r++) {
        vector<int> nd(n);
        for (int j = 0; j < n; j++) {
            int best = INT_MAX;
            for (int k = 0; k < n; k++) best = min(best, dp[k] + moveCost[grid[r - 1][k]][j]);
            nd[j] = best + grid[r][j];
        }
        dp = nd;
    }
    return *min_element(dp.begin(), dp.end());
}

JavaScript

var minPathCost = function(grid, moveCost) {
    var m = grid.length, n = grid[0].length, dp = grid[0].slice();
    for (var r = 1; r < m; r++) {
        var nd = new Array(n);
        for (var j = 0; j < n; j++) {
            var best = Infinity;
            for (var k = 0; k < n; k++) {
                var c = dp[k] + moveCost[grid[r - 1][k]][j];
                if (c < best) best = c;
            }
            nd[j] = best + grid[r][j];
        }
        dp = nd;
    }
    return Math.min.apply(null, dp);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming