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.lengthn == grid[i].length2 <= m, n <= 50grid is a permutation of 0..m*n-1moveCost.length == m * nmoveCost[i].length == n1 <= moveCost[i][j] <= 100
Hints for Minimum Path Cost in a Grid
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.
Hint 2
Let
dp[j]be the cheapest cost of a path ending at columnjof the current row (including that cell's value).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
- Start with
dp[j] = grid[0][j]for the first row. - For each next row
r, computenew[j] = grid[r][j] + min over k of (dp[k] + moveCost[grid[r-1][k]][j]). - Replace
dpwithnewand continue. - Return the minimum of
dpafter 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