Maximum Sum Path in a Matrix

Problem Statement

You are given an m x n matrix of integers. Starting from the top-left cell (0, 0), you need to reach the bottom-right cell (m-1, n-1). At each step, you can only move right or down. Find the maximum sum of values along any valid path.

Example 1:

Input: matrix = [[1, 3, 1],
                 [1, 5, 1],
                 [4, 2, 1]]
Output: 12
Explanation: Path 1 → 3 → 5 → 2 → 1 = 12

Example 2:

Input: matrix = [[5, 1],
                 [2, 8]]
Output: 15
Explanation: Path 5 → 2 → 8 = 15

Constraints:

1 <= m, n <= 200
-100 <= matrix[i][j] <= 100

Difficulty: Medium

Pattern Recognition

What is the input structure? A 2D grid of integers.
What are we optimizing? The sum of values along a path from top-left to bottom-right.
What pattern does this fit? Dynamic Programming (2D grid DP). Each cell's optimal value depends only on the cells above and to the left — classic overlapping subproblems with optimal substructure.
Why does this pattern fit? You can only arrive at a cell from the left or from above. The maximum sum to reach any cell is fully determined by the maximum sums of those two predecessor cells. This means you can build the solution bottom-up, one cell at a time.

Approach

Brute Force — Recursion

Try all valid paths by recursing right and down at each cell. Pick the maximum sum.

function maxPath(i, j):
    if i == m-1 and j == n-1:
        return matrix[i][j]
    if i >= m or j >= n:
        return -infinity
    return matrix[i][j] + max(maxPath(i+1, j), maxPath(i, j+1))

Time: O(2^(m+n)) — at each cell you branch into two choices. Space: O(m + n) — recursion stack depth. Why insufficient: Exponential time. For a 200x200 grid, this is completely intractable.

Optimal — Bottom-Up DP

Key Insight: Each cell dp[i][j] stores the maximum sum to reach that cell. You only need the value from the cell above and the cell to the left, so you can fill the table row by row in a single pass.

Step-by-step:

Create a DP table of the same dimensions as the matrix.
Initialize dp[0][0] = matrix[0][0].
Fill the first row: each cell can only come from the left, so dp[0][j] = dp[0][j-1] + matrix[0][j].
Fill the first column: each cell can only come from above, so dp[i][0] = dp[i-1][0] + matrix[i][0].
For all other cells: dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1]).
Return dp[m-1][n-1].

function maxPathDP(matrix):
    m, n = dimensions of matrix
    dp = m x n table
    dp[0][0] = matrix[0][0]
    for j in 1..n-1: dp[0][j] = dp[0][j-1] + matrix[0][j]
    for i in 1..m-1: dp[i][0] = dp[i-1][0] + matrix[i][0]
    for i in 1..m-1:
        for j in 1..n-1:
            dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

Time: O(m * n) — you visit each cell exactly once. Space: O(m * n) for the DP table. Can be reduced to O(n) with a single-row rolling array.

Walkthrough

Using the matrix:

[[1, 3, 1],
 [1, 5, 1],
 [4, 2, 1]]

Step 1 — Initialize and fill first row/column:

	j=0	j=1	j=2
i=0	1	4	5
i=1	2
i=2	6

dp[0][0] = 1
dp[0][1] = 1 + 3 = 4
dp[0][2] = 4 + 1 = 5
dp[1][0] = 1 + 1 = 2
dp[2][0] = 2 + 4 = 6

Step 2 — Fill remaining cells:

Processing dp[1][1]:

From above: dp[0][1] = 4
From left: dp[1][0] = 2
dp[1][1] = 5 + max(4, 2) = 9

Processing dp[1][2]:

From above: dp[0][2] = 5
From left: dp[1][1] = 9
dp[1][2] = 1 + max(5, 9) = 10

Processing dp[2][1]:

From above: dp[1][1] = 9
From left: dp[2][0] = 6
dp[2][1] = 2 + max(9, 6) = 11

Processing dp[2][2]:

From above: dp[1][2] = 10
From left: dp[2][1] = 11
dp[2][2] = 1 + max(10, 11) = 12

Final DP table:

	j=0	j=1	j=2
i=0	1	4	5
i=1	2	9	10
i=2	6	11	12

Answer: 12 — the path is 1 → 3 → 5 → 2 → 1.

Implementation

TypeScriptC++

typescript

function maxSumPath(matrix: number[][]): number {
    const m = matrix.length;
    const n = matrix[0].length;

    // dp[i][j] = max sum to reach cell (i, j)
    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
    dp[0][0] = matrix[0][0];

    // First row — can only come from the left
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }

    // First column — can only come from above
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }

    // Fill remaining cells
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = matrix[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

cpp

int maxSumPath(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();

    // dp[i][j] = max sum to reach cell (i, j)
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = matrix[0][0];

    // First row — can only come from the left
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }

    // First column — can only come from above
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }

    // Fill remaining cells
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = matrix[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

Space-optimized version (O(n) space):

TypeScriptC++

typescript

function maxSumPathOptimized(matrix: number[][]): number {
    const m = matrix.length;
    const n = matrix[0].length;

    // Only keep the current row
    let prev = new Array(n).fill(0);
    prev[0] = matrix[0][0];
    for (let j = 1; j < n; j++) {
        prev[j] = prev[j - 1] + matrix[0][j];
    }

    for (let i = 1; i < m; i++) {
        const curr = new Array(n).fill(0);
        curr[0] = prev[0] + matrix[i][0]; // First column — only from above
        for (let j = 1; j < n; j++) {
            curr[j] = matrix[i][j] + Math.max(prev[j], curr[j - 1]);
        }
        prev = curr;
    }

    return prev[n - 1];
}

cpp

int maxSumPathOptimized(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();

    // Only keep the current row
    vector<int> prev(n, 0);
    prev[0] = matrix[0][0];
    for (int j = 1; j < n; j++) {
        prev[j] = prev[j - 1] + matrix[0][j];
    }

    for (int i = 1; i < m; i++) {
        vector<int> curr(n, 0);
        curr[0] = prev[0] + matrix[i][0]; // First column — only from above
        for (int j = 1; j < n; j++) {
            curr[j] = matrix[i][j] + max(prev[j], curr[j - 1]);
        }
        prev = curr;
    }

    return prev[n - 1];
}

Watch out:

Forgetting to handle the first row and first column separately. These cells have only one predecessor, not two. If you apply the max(above, left) formula without initializing them, you will read out-of-bounds or use zeros incorrectly.
Modifying the input matrix in-place. This works but is risky in interviews — the interviewer may ask you not to mutate input. Mention this trade-off explicitly.
Assuming non-negative values. If the matrix can contain negative numbers, the greedy "always pick the bigger neighbor" at each step does not work — you need the full DP.

Complexity Analysis

	Time	Space
Brute Force (Recursion)	O(2^(m+n))	O(m + n)
Optimal (Bottom-Up DP)	O(m * n)	O(m * n)
Space-Optimized DP	O(m * n)	O(n)

Bottleneck: You must visit every cell at least once to account for its value, so O(m * n) time is optimal. The space bottleneck is the DP table, which the rolling-array technique reduces from O(m * n) to O(n).

Edge Cases

1x1 matrix — The answer is just matrix[0][0]. Make sure your loops handle m=1, n=1 without errors.
Single row or single column — Only one path exists. Your first-row/first-column initialization must handle this as the complete answer.
All negative values — The path sum will be negative. Ensure you are not initializing DP cells to 0 and then taking max (which would incorrectly prefer 0).
Large values near boundaries — The optimal path may hug the top row or left column entirely. Your DP handles this, but a greedy approach would fail.
Matrix with uniform values — Every path yields the same sum (m + n - 1) * value. Good sanity check.

LC 64 — Minimum Path Sum — Same grid movement, minimize instead of maximize. Identical DP structure.
LC 62 — Unique Paths — Count paths instead of summing values. Same DP recurrence shape, addition instead of max.
LC 120 — Triangle — Minimum path sum in a triangular grid. Same bottom-up DP idea, different shape.
LC 931 — Minimum Falling Path Sum — Move down to adjacent columns. Extends the pattern to three predecessors.

What is Expected at Each Level

Junior: Recognize that this is a DP problem. Write the recursive solution and explain why it is slow. Arrive at the O(m * n) DP with guidance.

Mid-level: Immediately identify the DP recurrence. Write clean bottom-up code with proper boundary handling. Discuss space optimization to O(n) and handle edge cases without prompting.

Senior: Write the space-optimized solution from the start. Discuss in-place modification trade-offs. Extend to variants (negative values, path reconstruction, diagonal movement). Analyze cache-friendliness of row-major vs column-major traversal.

Maximum Sum Path in a Matrix ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Recursion ​

Optimal — Bottom-Up DP ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

What is Expected at Each Level ​