Minimum Path Cost in a Grid solution and explanation
Google
8 more videos on this problem
Weekly Contest 297| Leetcode 2303 2304 2305 |Minimum Path Cost in a Grid| Fair Distribution CookiesCoding Decoded · 19:12 · 2K views
Leetcode 2304. Minimum Path Cost in a Grid | Contest 297 | HindiThinkCode · 9:47 · 2K views
2304 Minimum Path Cost in a Grid Leetcode Weekly Contest 297| Minimum Path Cost in a Grid LeetcodeAshutosh sharma · 11:42 · 1K views
2304. Minimum Path Cost in a Grid (Leetcode Medium)Programming Live with Larry · 13:17 · 1K views
Weekly Contest 297 | 2304. Minimum Path Cost in a GridcodingMohan · 10:07 · 741 views
Leetcode Weekly contest 297- Medium Minimum Path Cost in a GridPrakhar Agrawal · 11:34 · 289 views
Leetcode 2304. Minimum Path Cost in a GridElite Code · 28:47 · 260 views
2304. Minimum Path Cost in a Grid || Leetcode weekly contest || C++CS warriors · 9:20 · 191 views
2304 Minimum Path Cost in a Grid[CE] Code Engineering · 23:41 · 73 views
The problem
You are given a 0-indexed m x n integer matrix grid consisting of distinct integers from 0 to m * n - 1. You can move in this matrix from a cell to any other cell in the next row. That is, if you are in cell (x, y) such that x < m - 1, you can move to any of the cells (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1). Note that it is not possible to move from cells in the last row.
Each possible move has a cost given by a 0-indexed 2D array moveCost of size (m * n) x n, where moveCost[i][j] is the cost of moving from a cell with value i to a cell in column j of the next row. The cost of moving from cells in the last row of grid can be ignored.
The cost of a path in grid is the sum of all values of cells visited plus the sum of costs of all the moves made. Return the minimum cost of a path that starts from any cell in the first row and ends at any cell in the last row.
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: The path with the minimum possible cost is the path 5 -> 0 -> 1. - The sum of the values of cells visited is 5 + 0 + 1 = 6. - The cost of moving from 5 to 0 is 3. - The cost of moving from 0 to 1 is 8. So the total cost of the path is 6 + 3 + 8 = 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: The path with the minimum possible cost is the path 2 -> 3. - The sum of the values of cells visited is 2 + 3 = 5. - The cost of moving from 2 to 3 is 1. So the total cost of this path is 5 + 1 = 6.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 50gridconsists of distinct integers from0tom * n - 1.moveCost.length == m * nmoveCost[i].length == n1 <= moveCost[i][j] <= 100
Approach overview
Problem Overview: You are given a grid where you start from any cell in the first row and move down one row at a time. Moving from value v to column c in the next row adds an extra cost from the moveCost[v][c] table. The goal is to reach the last row with the minimum total cost including both cell values and movement costs.
Approach 1: Dynamic Programming (O(m * n^2) time, O(m * n) space)
The natural way to solve this is bottom-up dynamic programming. Define dp[r][c] as the minimum cost to reach cell (r, c). Initialize the first row with the grid values because you can start from any column. For every cell in row r, iterate over all columns in row r + 1 and update the transition using dp[r][c] + moveCost[grid[r][c]][nextCol] + grid[r+1][nextCol]. This effectively tries every valid downward move and keeps the minimum cost. Since each of the m * n cells can transition to n columns in the next row, the time complexity becomes O(m * n^2) with O(m * n) space (or O(n) with row compression). This approach directly models the problem and is the most common solution in interviews involving matrix transitions.
Approach 2: Greedy with Priority Queue (Dijkstra-style) (O(m * n^2 log(mn)) time, O(m * n) space)
You can also treat the grid as a weighted graph. Each cell (r, c) is a node, and it has edges to every cell in row r + 1. The edge weight equals moveCost[grid[r][c]][nextCol] + grid[r+1][nextCol]. Start by pushing all first-row cells into a min-heap with their grid values as initial costs. Then repeatedly pop the smallest cost state and relax edges to the next row using a priority queue from array-based grid positions. This behaves like Dijkstra's shortest path algorithm. The heap ensures the next processed state always has the smallest accumulated cost. Because each node may push up to n transitions and heap operations cost log(mn), the total complexity is O(m * n^2 log(mn)).
Recommended for interviews: The dynamic programming solution is what most interviewers expect. The grid naturally forms layered states (row by row), making the DP transition straightforward and easy to reason about. Mentioning the graph interpretation shows deeper understanding, but implementing DP with a clear transition and optionally compressing to O(n) space demonstrates stronger problem-solving skill.
Approach 1: Dynamic Programming Approach
In this approach, we use a dynamic programming table (often referred to as dp) to store the minimum cost to reach a cell in the grid from any cell in the previous row. The solution involves filling up this dp table row by row, using previously computed values to calculate the current values.
class Solution:
def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
dp = grid[0].copy()
for i in range(1, rows):
newDp = [float('inf')] * cols
for j in range(cols):
for k in range(cols):
from_val = grid[i - 1][k]
newDp[j] = min(newDp[j], dp[k] + moveCost[from_val][j] + grid[i][j])
dp = newDp
return min(dp)import java.util.*;
public class Solution {
public int minPathCost(int[][] grid, int[][] moveCost) {
int rows = grid.length;
int cols = grid[0].length;
int[] dp = Arrays.copyOf(grid[0], cols);
for (int i = 1; i < rows; i++) {
int[] newDp = new int[cols];
Arrays.fill(newDp, Integer.MAX_VALUE);
for (int j = 0; j < cols; j++) {
for (int k = 0; k < cols; k++) {
int from = grid[i - 1][k];
newDp[j] = Math.min(newDp[j], dp[k] + moveCost[from][j] + grid[i][j]);
}
}
dp = newDp;
}
return Arrays.stream(dp).min().getAsInt();
}
}#include <vector>
#include <algorithm>
int minPathCost(std::vector<std::vector<int>>& grid, std::vector<std::vector<int>>& moveCost) {
int rows = grid.size();
int cols = grid[0].size();
std::vector<int> dp(cols);
for (int j = 0; j < cols; ++j) {
dp[j] = grid[0][j];
}
for (int i = 1; i < rows; ++i) {
std::vector<int> newDp(cols, INT_MAX);
for (int j = 0; j < cols; ++j) {
for (int k = 0; k < cols; ++k) {
int from = grid[i - 1][k];
newDp[j] = std::min(newDp[j], dp[k] + moveCost[from][j] + grid[i][j]);
}
}
dp = newDp;
}
return *std::min_element(dp.begin(), dp.end());
}var minPathCost = function(grid, moveCost) {
const rows = grid.length;
const cols = grid[0].length;
let dp = [...grid[0]];
for (let i = 1; i < rows; i++) {
const newDp = new Array(cols).fill(Infinity);
for (let j = 0; j < cols; j++) {
for (let k = 0; k < cols; k++) {
const from = grid[i - 1][k];
newDp[j] = Math.min(newDp[j], dp[k] + moveCost[from][j] + grid[i][j]);
}
}
dp = newDp;
}
return Math.min(...dp);
};#include <stdio.h>
#include <limits.h>
int minPathCost(int** grid, int gridSize, int* gridColSize, int** moveCost, int moveCostSize, int* moveCostColSize) {
int rows = gridSize;
int cols = gridColSize[0];
int dp[cols];
for (int j = 0; j < cols; j++) {
dp[j] = grid[0][j];
}
for (int i = 1; i < rows; i++) {
int newDp[cols];
for (int j = 0; j < cols; j++) {
newDp[j] = INT_MAX;
for (int k = 0; k < cols; k++) {
int from = grid[i - 1][k];
newDp[j] = fmin(newDp[j], dp[k] + moveCost[from][j] + grid[i][j]);
}
}
for (int j = 0; j < cols; j++) {
dp[j] = newDp[j];
}
}
int minCost = INT_MAX;
for (int j = 0; j < cols; j++) {
minCost = fmin(minCost, dp[j]);
}
return minCost;
}using System;
public class Solution {
public int MinPathCost(int[][] grid, int[][] moveCost) {
int rows = grid.Length;
int cols = grid[0].Length;
int[] dp = (int[])grid[0].Clone();
for (int i = 1; i < rows; i++) {
int[] newDp = new int[cols];
Array.Fill(newDp, int.MaxValue);
for (int j = 0; j < cols; j++) {
for (int k = 0; k < cols; k++) {
int from = grid[i - 1][k];
newDp[j] = Math.Min(newDp[j], dp[k] + moveCost[from][j] + grid[i][j]);
}
}
dp = newDp;
}
return dp.Min();
}
}The Python solution uses lists to store and update the cost of reaching each cell. It initializes the cost list with the first row's values and iterates through each row, updating the minimum cost to move to each possible column using previous row's data.
Time complexity: O(m * n^2); Space complexity: O(n).
Approach 2: Greedy Approach with Priority Queue
This approach uses a priority queue (min-heap) to greedily explore paths with the least cost first. By maintaining a priority queue arranged by path costs, we can always expand the shortest path first, ensuring the minimum cost path is found efficiently.
import heapq
class Solution:
def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
pq = [(0, i, grid[0][i]) for i in range(n)] # (cost, column, value)
heapq.heapify(pq)
min_cost = float('inf')
while pq:
total_cost, col, value = heapq.heappop(pq)
row = value // n
if row == m - 1:
min_cost = min(min_cost, total_cost)
for new_col in range(n):
next_row_cost = grid[row+1][new_col]
move_cost = moveCost[value][new_col]
heapq.heappush(pq, (total_cost + next_row_cost + move_cost, new_col, grid[row+1][new_col]))
return min_costThis Python implementation uses a priority queue (using the heapq module) to maintain paths by their cumulative cost. By always expanding the path with the smallest cost first, it ensures that we find the minimum cost path optimally.
Time complexity: O(m * n log n); Space complexity: O(m * n).
Approach 3: Dynamic Programming
We define f[i][j] to represent the minimum path cost from the first row to the ith row and jth column. Since we can only move from a column in the previous row to a column in the current row, the value of f[i][j] can be transferred from f[i - 1][k], where the range of k is [0, n - 1]. Therefore, the state transition equation is:
$
f[i][j] = min_{0 leq k < n} {f[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j]}
where moveCost[grid[i - 1][k]][j] represents the cost of moving from the kth column of the i - 1th row to the jth column of the ith row.
The final answer is min_{0 leq j < n} {f[m - 1][j]}.
Since each transition only needs the state of the previous row, we can use a rolling array to optimize the space complexity to O(n).
The time complexity is O(m times n^2), and the space complexity is O(n). Here, m and n$ are the number of rows and columns of the grid, respectively.
function minPathCost(grid: number[][], moveCost: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const f = grid[0];
for (let i = 1; i < m; ++i) {
const g: number[] = Array(n).fill(Infinity);
for (let j = 0; j < n; ++j) {
for (let k = 0; k < n; ++k) {
g[j] = Math.min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
}
}
f.splice(0, n, ...g);
}
return Math.min(...f);
}func minPathCost(grid [][]int, moveCost [][]int) int {
m, n := len(grid), len(grid[0])
f := grid[0]
for i := 1; i < m; i++ {
g := make([]int, n)
for j := 0; j < n; j++ {
g[j] = 1 << 30
for k := 0; k < n; k++ {
g[j] = min(g[j], f[k]+moveCost[grid[i-1][k]][j]+grid[i][j])
}
}
f = g
}
return slices.Min(f)
}impl Solution {
pub fn min_path_cost(grid: Vec<Vec<i32>>, move_cost: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut f = grid[0].clone();
for i in 1..m {
let mut g: Vec<i32> = vec![i32::MAX; n];
for j in 0..n {
for k in 0..n {
g[j] = g[j].min(f[k] + move_cost[grid[i - 1][k] as usize][j] + grid[i][j]);
}
}
f.copy_from_slice(&g);
}
f.iter().cloned().min().unwrap_or(0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time complexity: O(m * n^2); Space complexity: O(n). |
| Greedy Approach with Priority Queue | Time complexity: O(m * n log n); Space complexity: O(m * n). |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(m * n^2) | O(m * n) or O(n) | Best general solution. Directly models row-to-row transitions and is easy to implement in interviews. |
| Greedy with Priority Queue (Dijkstra) | O(m * n^2 log(mn)) | O(m * n) | Useful when thinking of the grid as a weighted graph or when applying shortest path algorithms. |
Frequently asked questions
Is Minimum Path Cost in a Grid easy or hard?
Minimum Path Cost in a Grid is a Medium-level problem. The main challenge is recognizing the DP state and correctly applying the transition using the moveCost matrix between rows.
Minimum Path Cost in a Grid Python or Java solution
Most implementations use dynamic programming with nested loops. Maintain a DP array for the current row and update the next row using the moveCost lookup. The same logic works in Python, Java, C++, C#, and JavaScript with O(m * n^2) complexity.
How to solve Minimum Path Cost in a Grid in O(m * n^2)?
Use dynamic programming. Initialize the first row with grid values, then iterate row by row. For each cell (r, c), try moving to every column in row r+1 and update dp[r+1][nextCol] using dp[r][c] + moveCost[grid[r][c]][nextCol] + grid[r+1][nextCol]. Track the minimum cost in the final row.
What is the best approach for Minimum Path Cost in a Grid?
Dynamic programming is the best approach. Define dp[r][c] as the minimum cost to reach cell (r, c) and compute transitions to the next row using the moveCost table. This approach runs in O(m * n^2) time and O(m * n) space, and it directly models the row-by-row structure of the grid.
What data structure is used in Minimum Path Cost in a Grid?
The main structure is a dynamic programming table built on top of a matrix. Some alternative solutions model the grid as a graph and use a priority queue (min-heap) to run a Dijkstra-style shortest path search.
What is the time complexity of Minimum Path Cost in a Grid?
The optimal dynamic programming solution runs in O(m * n^2) time because each of the m * n cells can transition to n columns in the next row. Space complexity is O(m * n) for the DP table, which can be reduced to O(n) by keeping only the previous row.
Is Minimum Path Cost in a Grid asked at Google, Amazon, or Meta?
Grid dynamic programming problems with transition cost tables frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of minimum path problems and layered DP over matrices are common interview patterns.