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] <= 200Problem Overview: You are given an m x n grid where each cell contains a non‑negative cost. Starting from the top-left corner, move only right or down until reaching the bottom-right cell. The goal is to compute the minimum possible sum of values along that path.
Approach 1: Dynamic Programming with Extra Space (Time: O(m*n), Space: O(m*n))
The classic solution uses a 2D DP table where dp[i][j] represents the minimum path sum required to reach cell (i, j). Start by initializing the first row and first column because those cells can only be reached from one direction. For every other cell, compute dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). This works because every valid path must come from either the cell above or the cell to the left. The approach is straightforward and easy to reason about, which makes it a good starting point when practicing dynamic programming on grid problems.
Approach 2: Dynamic Programming with In-Place Modification (Time: O(m*n), Space: O(1))
The DP state can be stored directly inside the input grid to remove the extra memory. Iterate through the matrix row by row and update each cell to represent the minimum cost to reach that position. For the first row, accumulate values from the left; for the first column, accumulate from above. For all other cells, update using grid[i][j] += min(grid[i-1][j], grid[i][j-1]). After processing the entire grid, the bottom-right cell contains the answer. This version keeps the same time complexity but reduces space to constant because it reuses the matrix. It is a common optimization pattern in matrix DP problems.
Alternative Thought Process: Recursive Exploration
A naive recursive strategy explores both choices (move right or move down) from every cell and returns the minimum path sum. Without memoization this leads to repeated recomputation and exponential time complexity O(2^(m+n)). Adding memoization converts the recursion into the same dynamic programming structure described above. Understanding this transition from brute-force recursion to DP is key when solving many array and grid optimization problems.
Recommended for interviews: Interviewers expect the dynamic programming solution with O(m*n) time. Starting with the DP table version clearly shows the recurrence relation and state definition. Once that is established, optimizing to the in-place version demonstrates strong problem-solving skills and awareness of space optimization.
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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the additional 2D array used.
| Approach | Complexity |
|---|---|
| Dynamic Programming with In-Place Modification | 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. |
| Dynamic Programming with Extra Space | Time Complexity: O(m * n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Brute Force | O(2^(m+n)) | O(m+n) | Conceptual starting point to understand exploring right/down paths |
| Dynamic Programming (Extra 2D Array) | O(m*n) | O(m*n) | Best for clarity when learning DP or explaining the recurrence in interviews |
| Dynamic Programming (In-Place Grid Update) | O(m*n) | O(1) | Preferred when memory is constrained or when optimizing the DP solution |
DP 10. Minimum Path Sum in Grid | Asked to me In Microsoft Internship Interview | DP on GRIDS • take U forward • 283,192 views views
Watch 9 more video solutions →Practice Minimum Path Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor