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] <= 200The Minimum Path Sum problem asks you to find the smallest possible sum of values when moving from the top-left cell to the bottom-right cell of a grid. You are only allowed to move right or down at any step. A brute-force approach would try every possible path, but that quickly becomes inefficient as the grid grows.
A better approach uses Dynamic Programming. The key idea is that the minimum cost to reach any cell depends on the minimum cost of reaching the cell directly above or to the left. By storing these intermediate results, you avoid recomputing paths repeatedly. You can either use a separate DP matrix or update the grid in-place to save space.
By iterating through the grid and updating each cell with the minimum cumulative sum, you build the optimal solution step by step. This approach processes each cell once, making it efficient for large grids.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Grid Traversal) | O(m × n) | O(1) to O(m × n) |
take U forward
This approach involves modifying the input grid in place to store the minimum path sum to each cell. Since we can only move right or down, the minimum path sum to each cell is the value of that cell plus the minimum of the sum from the above or left cell. Start by updating the first row and column as they can only be reached by a single direction. Then, fill in the rest of the grid by selecting the minimum path from top or left for each cell.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, as each cell is visited once.
Space Complexity: O(1) as we modify the grid in place.
1#include <stdio.h>
2
3int minPathSum(int** grid, int gridSize, int* gridColSize) {
4 for(int i = 1
This C code uses nested loops to update the grid in place. The first loop updates the first column, and the second loop updates the first row. Then the nested loops calculate the minimum path sum for the rest of the grid by considering the minimum of the top and left cells. The function returns the bottom-right corner of the grid, which now contains the minimum path sum.
Rather than modifying the input grid, this approach uses an additional 2D array to store the minimum path sums. Start by initializing the first cell to the first cell of the grid. For the first row and first column, accumulate sums as they can only come from one direction. For the rest of the cells, compute the minimum path by taking the minimum of the paths leading from the top or left cell, and store the result in the auxiliary DP array.
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the additional 2D array used.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, recursion with memoization can solve the problem by exploring paths and caching results. However, a bottom-up dynamic programming approach is usually preferred because it avoids recursion overhead and is more space efficient.
Yes, grid-based dynamic programming problems like Minimum Path Sum are common in technical interviews at companies like FAANG. They test understanding of DP transitions, optimization, and matrix traversal techniques.
The optimal approach uses dynamic programming. Each cell stores the minimum sum required to reach it by considering the minimum of the top or left neighbor plus the current cell value. This avoids recomputing paths and ensures efficient traversal of the grid.
A 2D array (or the input grid itself) works best for this problem because it naturally represents the grid structure. Dynamic programming values can be stored in the same grid to reduce extra memory usage.
This C solution uses a separate 2D array to store the computed minimum path sums. Memory is dynamically allocated for storing sums; after computing the path, memory is freed.