Log inSign up
mediumGeeksforGeeksNot Started

Maximum Path Sum in Matrix

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

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an N × M matrix mat of positive integers, you need to find the maximum path sum starting from any cell in the first row and ending at any cell in the last row.

From cell (i, j), you are allowed to move to: 1. Directly down: (i + 1, j) 2. Diagonally left down: (i + 1, j - 1) 3. Diagonally right down: (i + 1, j + 1)

### Example 1 - Input: ``text mat = [ [1, 2, 10, 4], [100, 3, 2, 1], [1, 1, 20, 2], [1, 2, 2, 1] ] ` - **Output**: 105 - **Explanation**: Start at mat[0][2]=10 -> mat[1][0]=100? No, from mat[0][1]=2 we can reach mat[1][0]=100! Path: mat[0][1]=2 -> mat[1][0]=100 -> mat[2][1]=1 -> mat[3][1]=2 = 105`.

### Example 2 - Input: ``text mat = [ [1, 2, 3], [9, 8, 7], [4, 5, 6] ] ` - **Output**: 17 - **Explanation**: Path 3 -> 8 -> 6 = 17 or 2 -> 9 -> 5 = 16. Maximum is 3 -> 8 -> 6 = 17`.

Constraints:

  • 1 <= N, M <= 500
  • -104 <= mat[i][j] <= 104

What You'll Learn

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

  • Master multi-start and multi-destination grid DP.
  • Formulate transitions involving boundary checks.
  • Optimize 2D grid DP memory to O(M) single-row storage.

Pattern Recognition Trigger

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

Signals to Look For:

  • Grid path traversal strictly down / down-diagonal.
  • Multi-source start (any col in row 0) and multi-destination end (any col in row N-1).
  • Maximizing accumulated value along path.

Algorithmic Decision Tree:

  • Check left and right boundary conditions (j - 1 >= 0 and j + 1 < M).
  • Iterate row from 1 to N-1.

Connected Patterns:

Gold Mine ProblemMinimum Falling Path SumTriangle Minimum Path Sum

1. Recursive Multi-Source DFS

Intuition

Explore all 3 recursive branches from every cell in row 0 down to row N-1.

Algorithm

  1. Define helper dfs(r, c).
  2. If c < 0 || c >= M, return -\infty.
  3. If r == 0, return mat[0][c].
  4. Otherwise, return mat[r][c] + max({ dfs(r-1, c-1), dfs(r-1, c), dfs(r-1, c+1) }).
  5. Evaluate for all columns in row N-1 and take the max.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8class Solution {
9 int dfs(int r, int c, const vector<vector<int>>& mat, int n, int m) {
10 if (c < 0 || c >= m) return -1e9;
11 if (r == 0) return mat[0][c];
12 int up = dfs(r - 1, c, mat, n, m);
13 int upLeft = dfs(r - 1, c - 1, mat, n, m);
14 int upRight = dfs(r - 1, c + 1, mat, n, m);
15 return mat[r][c] + max({up, upLeft, upRight});
16 }
17public:
18 int maximumPath(int n, int m, vector<vector<int>>& mat) {
19 int maxVal = -1e9;
20 for (int j = 0; j < m; ++j) {
21 maxVal = max(maxVal, dfs(n - 1, j, mat, n, m));
22 }
23 return maxVal;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<vector<int>> mat = {
30 {1, 2, 10, 4},
31 {100, 3, 2, 1},
32 {1, 1, 20, 2},
33 {1, 2, 2, 1}
34 };
35 cout << "Max Path Sum: " << sol.maximumPath(4, 4, mat) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(M * 3^N)
  • Space complexity: O(N) call stack

2. Memoized Top-Down DP

Intuition

Store intermediate results in an N x M memoization table to eliminate overlapping subproblems.

Algorithm

  1. Initialize memo[N][M] with -1.
  2. In dfs(r, c), return memo[r][c] if already computed.
  3. Store result in memo[r][c] and return.
  4. Check all endpoints in bottom row.
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>>& mat, int n, int m, vector<vector<int>>& memo) {
9 if (c < 0 || c >= m) return -1e9;
10 if (r == 0) return mat[0][c];
11 if (memo[r][c] != -1e9) return memo[r][c];
12
13 int up = solve(r - 1, c, mat, n, m, memo);
14 int upLeft = solve(r - 1, c - 1, mat, n, m, memo);
15 int upRight = solve(r - 1, c + 1, mat, n, m, memo);
16
17 return memo[r][c] = mat[r][c] + max({up, upLeft, upRight});
18 }
19public:
20 int maximumPath(int n, int m, vector<vector<int>>& mat) {
21 vector<vector<int>> memo(n, vector<int>(m, -1e9));
22 int maxVal = -1e9;
23 for (int j = 0; j < m; ++j) {
24 maxVal = max(maxVal, solve(n - 1, j, mat, n, m, memo));
25 }
26 return maxVal;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<vector<int>> mat = {
33 {1, 2, 10, 4},
34 {100, 3, 2, 1},
35 {1, 1, 20, 2},
36 {1, 2, 2, 1}
37 };
38 cout << "Max Path Sum: " << sol.maximumPath(4, 4, mat) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N * M)
  • Space complexity: O(N * M) memo table + O(N) recursion stack

3. Space-Optimized Iterative DP (Rolling Array)

Intuition

Compute iteratively row by row from top to bottom, maintaining only a single 1D array representing the previous row.

Algorithm

  1. Initialize prev array of size M with row 0 values.
  2. Loop row i from 1 to N-1:
  3. Initialize curr array of size M.
  4. For each column j from 0 to M-1:
  5. curr[j] = mat[i][j] + max(prev[j], (j>0 ? prev[j-1] : -inf), (j<M-1 ? prev[j+1] : -inf)).
  6. Set prev = curr.
  7. Return the maximum value in prev.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximumPath(int n, int m, vector<vector<int>>& mat) {
10 vector<int> prev = mat[0];
11
12 for (int i = 1; i < n; ++i) {
13 vector<int> curr(m, 0);
14 for (int j = 0; j < m; ++j) {
15 int up = prev[j];
16 int upLeft = (j > 0) ? prev[j - 1] : -1e9;
17 int upRight = (j < m - 1) ? prev[j + 1] : -1e9;
18 curr[j] = mat[i][j] + max({up, upLeft, upRight});
19 }
20 prev = move(curr);
21 }
22
23 return *max_element(prev.begin(), prev.end());
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<vector<int>> mat = {
30 {1, 2, 10, 4},
31 {100, 3, 2, 1},
32 {1, 1, 20, 2},
33 {1, 2, 2, 1}
34 };
35 cout << "Max Path Sum: " << sol.maximumPath(4, 4, mat) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N * M)
  • Space complexity: O(M)

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(M * 3^N)O(N)Recursively explore all 3 paths down to row N-1.Overlapping subproblem recalculation
2.Memoized Top-Down DPO(N * M)O(N * M)Cache subproblem results in a 2D memo table.Recursion depth
3.1D Rolling Row DPOptimalO(N * M)O(M)Row-by-row tabulation keeping only the previous row.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using 0 instead of -infinity for out-of-bound diagonals when values in matrix can be negative.

Pitfall 2:

Forgetting to check boundary conditions (j - 1 >= 0 and j + 1 < M).

Crucial Edge Cases to Validate:

  • N = 1: Single row; answer is the maximum element in that row.
  • M = 1: Single column; the only path is straight down (sum of all elements in column).
  • Negative numbers: Must initialize out-of-bound sentinel values to -infinity, not 0.

Interview Tips & Best Practices

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

  1. Highlight that this problem is symmetric to Gold Mine (Gold Mine transitions column-to-column, while Maximum Path Sum transitions row-to-row).

Quick Comprehension Check

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

1.Why can the space complexity of Maximum Path Sum in Matrix be reduced from O(N * M) to O(M)?

Back to DSA Sheet