Log inSign up
mediumLeetCodeNot Started

Minimum Path Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given a m x n grid filled with non-negative numbers, find a path from top left (0, 0) to bottom right (m - 1, n - 1), 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: ``text 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: ``text grid = [ [1, 2, 3], [4, 5, 6] ] ` - **Output**: 12`

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate classic 2D grid path recurrence relations.
  • Handle grid boundary initialization cleanly.
  • Space-optimize 2D grid DP from O(m * n) to O(n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Grid traversal from (0,0) to (m-1, n-1).
  • Only moves allowed: right and down.
  • Minimizing path sum.

Algorithmic Decision Tree:

  • Initialize dp[0] carefully on row transitions.
  • dp[j] represents value from previous row (up), dp[j-1] represents value from current row (left).

Connected Patterns:

Unique PathsUnique Paths IIMaximum Path Sum in Matrix

1. Recursive Exploration

Intuition

Recursively branch into moving down and right from (0, 0) to (m - 1, n - 1).

Algorithm

  1. Define solve(r, c).
  2. If r >= m || c >= n, return \infty.
  3. If r == m - 1 && c == n - 1, return grid[r][c].
  4. Return grid[r][c] + min(solve(r + 1, c), solve(r, c + 1)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c, const vector<vector<int>>& grid) {
9 int m = grid.size(), n = grid[0].size();
10 if (r == m - 1 && c == n - 1) return grid[r][c];
11 if (r >= m || c >= n) return 1e9;
12 return grid[r][c] + min(solve(r + 1, c, grid), solve(r, c + 1, grid));
13 }
14public:
15 int minPathSum(vector<vector<int>>& grid) {
16 return solve(0, 0, grid);
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
23 cout << "Min Path Sum: " << sol.minPathSum(grid) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^(m + n))
  • Space complexity: O(m + n) call stack

2. 2D Tabulation DP (O(m * n) Space)

Intuition

Allocate a 2D matrix dp[m][n] and fill from top-left to bottom-right.

Algorithm

  1. Initialize dp[m][n].
  2. dp[0][0] = grid[0][0].
  3. Initialize first row: dp[0][j] = dp[0][j-1] + grid[0][j].
  4. Initialize first col: dp[i][0] = dp[i-1][0] + grid[i][0].
  5. For i from 1 to m - 1 and j from 1 to n - 1:
  6. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
  7. Return dp[m-1][n-1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minPathSum(vector<vector<int>>& grid) {
10 int m = grid.size(), n = grid[0].size();
11 vector<vector<int>> dp(m, vector<int>(n, 0));
12 dp[0][0] = grid[0][0];
13
14 for (int j = 1; j < n; ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
15 for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
16
17 for (int i = 1; i < m; ++i) {
18 for (int j = 1; j < n; ++j) {
19 dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
20 }
21 }
22
23 return dp[m - 1][n - 1];
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
30 cout << "Min Path Sum: " << sol.minPathSum(grid) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Rolling Row DP (O(n) Space)

Intuition

Maintain a single 1D array of size n. Update in-place from left to right for each row.

Algorithm

  1. Initialize 1D array dp of size n.
  2. Initialize row 0: dp[0] = grid[0][0], dp[j] = dp[j-1] + grid[0][j].
  3. For row i from 1 to m - 1:
  4. dp[0] += grid[i][0] (only way is down from above).
  5. For column j from 1 to n - 1:
  6. dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
  7. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minPathSum(vector<vector<int>>& grid) {
10 int m = grid.size(), n = grid[0].size();
11 vector<int> dp(n, 0);
12 dp[0] = grid[0][0];
13
14 for (int j = 1; j < n; ++j) dp[j] = dp[j - 1] + grid[0][j];
15
16 for (int i = 1; i < m; ++i) {
17 dp[0] += grid[i][0];
18 for (int j = 1; j < n; ++j) {
19 dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
20 }
21 }
22
23 return dp[n - 1];
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
30 cout << "Min Path Sum: " << sol.minPathSum(grid) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(2^(m + n))O(m + n)Exhaustive branching over down and right moves.Overlapping subproblem computation
2.2D Tabulation DPO(m * n)O(m * n)Fill an explicit m x n grid of prefix path sums.Auxiliary grid memory
3.1D Rolling Row DPOptimalO(m * n)O(n)Maintain only one row of size n updated in-place.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to update dp[0] on each new row in the 1D approach (dp[0] += grid[i][0]).

Pitfall 2:

Overwriting grid directly in interviews without asking if mutating the input is permitted.

Crucial Edge Cases to Validate:

  • 1x1 grid: Directly returns grid[0][0].
  • 1xN grid (single row): Sum of all elements in the row.
  • Mx1 grid (single column): Sum of all elements in the column.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that while modifying grid in-place gives O(1) extra space, in production environments mutating inputs is often an anti-pattern, making the O(n) auxiliary 1D array preferable.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When updating dp[j] in the 1D rolling array approach, where do the values for above and left come from?

Back to DSA Sheet