Minimum Path Sum
MedPrompt
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.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
Approaches
5 approaches with complexity analysis and trade-offs.
The most intuitive approach is to try every possible path from the top-left to the bottom-right corner. Since we can only move right or down, we can use recursion to explore both moves from any given cell. We then find the path that results in the minimum sum.
Algorithm
- Define a recursive function
calculate(grid, i, j). - Base Case: If
iorjare out of bounds, return a very large number (infinity) to signify an invalid path. - Base Case: If
(i, j)is the bottom-right corner(m-1, n-1), returngrid[i][j]. - Recursive Step: Recursively call the function for the cell below
(i+1, j)and the cell to the right(i, j+1). - Return
grid[i][j] + min(result_from_down, result_from_right). - The initial call is
calculate(grid, 0, 0).
Walkthrough
We can define a recursive function, say calculate(grid, i, j), that computes the minimum path sum from the cell (i, j) to the destination at (m-1, n-1).
For any cell (i, j), the path can continue either down to (i+1, j) or right to (i, j+1). Therefore, the minimum path sum from (i, j) is its own value grid[i][j] plus the minimum of the path sums starting from these two adjacent cells.
The base case for the recursion is the destination cell (m-1, n-1). The minimum path from the destination to itself is just its own value. If a recursive call goes out of the grid's boundaries, it represents an invalid path, so we return a value equivalent to infinity to ensure it's never chosen as the minimum.
This method explores all possible paths, but because many paths will cross over the same cells, it ends up re-calculating the minimum path sum from those cells multiple times.
class Solution { public int minPathSum(int[][] grid) { return calculate(grid, 0, 0); } private int calculate(int[][] grid, int i, int j) { int m = grid.length; int n = grid[0].length; if (i >= m || j >= n) { return Integer.MAX_VALUE; } if (i == m - 1 && j == n - 1) { return grid[i][j]; } // To avoid integer overflow when adding grid[i][j], we find the min first. int minOfNextSteps = Math.min(calculate(grid, i + 1, j), calculate(grid, i, j + 1)); return grid[i][j] + minOfNextSteps; }}Complexity
Time
O(2^(m+n))
Space
O(m + n)
Trade-offs
Pros
Simple to conceptualize and implement.
Follows the problem's constraints (down or right moves) directly.
Cons
Extremely inefficient due to a large number of redundant calculations for the same subproblems.
Will result in a 'Time Limit Exceeded' error for all but the smallest grids.
The brute-force approach is slow because it re-computes the minimum path sum for the same cells multiple times. We can significantly improve performance by caching the results of these subproblems. This technique, where we use a recursive structure but store results to avoid re-computation, is known as memoization or top-down dynamic programming.
Algorithm
- Create a 2D
memoarray of the same size asgrid, initialized with a sentinel value (e.g., -1). - Define a recursive function
calculate(grid, i, j, memo). - Handle base cases for out-of-bounds and destination cell as in the brute-force approach.
- Before computing, check if
memo[i][j]is already computed. If so, return the stored value. - If not, recursively compute the minimum sum from the 'down' and 'right' paths.
- Store the result in
memo[i][j]before returning:memo[i][j] = grid[i][j] + min(down, right).
Walkthrough
We introduce a 2D array, memo, with the same dimensions as the input grid. This memo table will store the results of our calculate(i, j) function. Each cell memo[i][j] is initialized to a value that indicates it hasn't been computed yet (e.g., -1).
Inside the recursive function, before performing any calculations for cell (i, j), we first check if memo[i][j] contains a valid pre-computed result. If it does, we return it immediately. Otherwise, we perform the calculation as in the brute-force approach. Once the result is computed, we store it in memo[i][j] before returning. This ensures that the minimum path sum for each cell is calculated exactly once.
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] memo = new int[m][n]; for (int[] row : memo) { java.util.Arrays.fill(row, -1); } return calculate(grid, 0, 0, memo); } private int calculate(int[][] grid, int i, int j, int[][] memo) { int m = grid.length; int n = grid[0].length; if (i >= m || j >= n) { return Integer.MAX_VALUE; } if (i == m - 1 && j == n - 1) { return grid[i][j]; } if (memo[i][j] != -1) { return memo[i][j]; } int minOfNextSteps = Math.min(calculate(grid, i + 1, j, memo), calculate(grid, i, j + 1, memo)); memo[i][j] = grid[i][j] + minOfNextSteps; return memo[i][j]; }}Complexity
Time
O(m * n)
Space
O(m * n)
Trade-offs
Pros
Drastically improves time complexity by eliminating redundant computations.
Guarantees that each subproblem is solved only once.
Cons
Requires extra space for the memoization table, which is O(m*n).
Can still lead to a stack overflow error on very large grids due to deep recursion, although the constraints (m, n <= 200) make this less likely.
We can also solve this problem iteratively using a bottom-up approach. We build the solution from the start (0,0) towards the end (m-1, n-1). We use a 2D DP table where dp[i][j] stores the minimum path sum to reach cell (i,j).
Algorithm
- Create a 2D
dparray of sizem x n. dp[i][j]will store the minimum path sum from(0,0)to(i,j).- Initialize the top-left cell:
dp[0][0] = grid[0][0]. - Fill the first row:
dp[0][j] = dp[0][j-1] + grid[0][j]. - Fill the first column:
dp[i][0] = dp[i-1][0] + grid[i][0]. - Iterate through the rest of the grid from
(1,1)to(m-1,n-1)and filldp[i][j]using the relation:dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). - The final answer is
dp[m-1][n-1].
Walkthrough
We create a 2D array dp of the same size as the grid. The value dp[i][j] will represent the minimum sum of a path from the top-left corner (0,0) to the cell (i,j).
The state transition is based on the fact that to reach cell (i,j), we must have come from either the cell above, (i-1,j), or the cell to the left, (i,j-1). Therefore, the minimum path sum to (i,j) is grid[i][j] plus the minimum of the path sums to its top and left neighbors.
We fill the dp table by first initializing the base cases (the first row and first column) and then iterating through the rest of the cells, applying the transition formula. The final answer is the value in the bottom-right corner of the dp table.
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; // Initialize first row for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // Initialize first column for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // Fill the rest of the dp table for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; }}Complexity
Time
O(m * n)
Space
O(m * n)
Trade-offs
Pros
Efficient with a polynomial time complexity.
Avoids recursion, which can prevent stack overflow issues and may have slightly better performance due to lower overhead.
Cons
Requires O(m*n) extra space for the DP table, same as the memoization approach.
Observing the 2D DP recurrence relation, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), we can see that to compute the values for the current row i, we only need the values from the previous row i-1. This insight allows us to optimize the space complexity by using a 1D array instead of a 2D table.
Algorithm
- Create a 1D
dparray of sizen(number of columns). - Initialize the
dparray by computing the path sums for the first row of the grid. - Iterate from the second row (
i=1) to the last row (m-1):- Update the first element
dp[0]for the current row:dp[0] = dp[0] + grid[i][0]. - Iterate from the second column (
j=1) to the last column (n-1): - Update
dp[j]using the formula:dp[j] = min(dp[j], dp[j-1]) + grid[i][j].
- Update the first element
- The final answer is
dp[n-1].
Walkthrough
Instead of a 2D dp table, we use a 1D array, dp, of size n. This dp array will store the minimum path sums for the cells in the current row being processed.
We start by initializing the dp array with the path sums for the first row. Then, we iterate through the remaining rows of the grid one by one. For each new row i, we update the dp array. The new dp[j] (for row i) is calculated using the old dp[j] (which represents the value from row i-1) and the new dp[j-1] (which represents the value from the current row i at the previous column).
The update for dp[0] is special as it can only come from above. For other dp[j], it's the minimum of the value from above (the old dp[j]) and the value from the left (the new dp[j-1]), plus the grid value. After processing all rows, dp[n-1] will hold the final answer.
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] dp = new int[n]; // Initialize dp array with the first row's path sums dp[0] = grid[0][0]; for (int j = 1; j < n; j++) { dp[j] = dp[j - 1] + grid[0][j]; } // Iterate over the rest of the rows for (int i = 1; i < m; i++) { // Update the first column's path sum for the current row dp[0] = dp[0] + grid[i][0]; // Update the rest of the columns for the current row for (int j = 1; j < n; j++) { dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; } } return dp[n - 1]; }}Complexity
Time
O(m * n)
Space
O(n)
Trade-offs
Pros
Highly space-efficient, reducing space from O(m*n) to O(n) or O(min(m,n)).
Maintains the optimal time complexity of O(m*n).
Cons
The logic can be slightly more complex to reason about compared to the 2D DP approach.
This is the most space-efficient dynamic programming solution. We can eliminate the need for any extra space (besides a few variables) by using the input grid itself as our DP table. The original value of grid[i][j] is only needed once to compute the cumulative path sum to that cell, so we can overwrite it with the result.
Algorithm
- Use the input
griditself as the DP table. - Update the first row:
grid[0][j] = grid[0][j] + grid[0][j-1]forjfrom 1 ton-1. - Update the first column:
grid[i][0] = grid[i][0] + grid[i-1][0]forifrom 1 tom-1. - Iterate through the rest of the grid from
(1,1). - Update each cell with the formula:
grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]). - Return the value at the bottom-right corner,
grid[m-1][n-1].
Walkthrough
The logic is identical to the 2D bottom-up DP approach, but all updates are performed directly on the input grid. grid[i][j] is repurposed to store the minimum path sum from (0,0) to (i,j).
We first pre-process the first row and first column, as their minimum path sums are straightforward to calculate (they can only be reached from one direction). Then, we iterate through the rest of the grid, updating each grid[i][j] by adding its original value to the minimum of the already-updated values in the cell above (grid[i-1][j]) and to the left (grid[i][j-1]).
After the loops complete, the entire grid is filled with cumulative path sums, and the value at grid[m-1][n-1] is our final answer.
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; // Update first row for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; } // Update first column for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; } // Update the rest of the grid for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; }}Complexity
Time
O(m * n)
Space
O(1)
Trade-offs
Pros
Optimal space complexity, as no extra space proportional to the input size is used.
Very efficient in both time and space.
Cons
This approach modifies the input grid, which might be undesirable if the original grid needs to be preserved.
Solutions
Solution
public class Solution { public int MinPathSum(int[][] grid) { int m = grid.Length, n = grid[0].Length; int[, ] f = new int[m, n]; f[0, 0] = grid[0][0]; for (int i = 1; i < m; ++i) { f[i, 0] = f[i - 1, 0] + grid[i][0]; } for (int j = 1; j < n; ++j) { f[0, j] = f[0, j - 1] + grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { f[i, j] = Math.Min(f[i - 1, j], f[i, j - 1]) + grid[i][j]; } } return f[m - 1, n - 1]; }}class Solution {public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] f = new int[m][n]; f[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (int j = 1; j < n; ++j) { f[0][j] = f[0][j - 1] + grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } return f[m - 1][n - 1]; }}/** * @param {number[][]} grid * @return {number} */ var minPathSum = function ( grid,) { const m = grid.length; const n = grid[0].length; const f = Array(m) .fill(0) .map(() => Array(n).fill(0)); f[0][0] = grid[0][0]; for (let i = 1; i < m; ++i) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (let j = 1; j < n; ++j) { f[0][j] = f[0][j - 1] + grid[0][j]; } for (let i = 1; i < m; ++i) { for (let j = 1; j < n; ++j) { f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } return f[m - 1][n - 1];};class Solution {public: int minPathSum(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int f[m][n]; f[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (int j = 1; j < n; ++j) { f[0][j] = f[0][j - 1] + grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } return f[m - 1][n - 1]; }};class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[0] * n for _ in range(m)] f[0][0] = grid[0][0] for i in range(1, m): f[i][0] = f[i - 1][0] + grid[i][0] for j in range(1, n): f[0][j] = f[0][j - 1] + grid[0][j] for i in range(1, m): for j in range(1, n): f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j] return f[- 1][- 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.