64. Minimum Path Sum DP Solution

The problem

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.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Approach overview

Problem Overview: You are given an m x n grid filled with non‑negative numbers. Starting at the top-left cell, move only right or down until reaching the bottom-right cell. The goal is to compute the minimum possible sum of all values along the path.

Approach 1: Recursive Exploration (Exponential Time)

The most straightforward idea is to explore every possible path using recursion. From any cell (i, j), you have two choices: move right to (i, j+1) or down to (i+1, j). Recursively compute the path sum for both directions and take the minimum. This works but recomputes the same subproblems many times. The time complexity becomes O(2^(m+n)) with O(m+n) recursion stack space, which quickly becomes infeasible for larger grids.

Approach 2: Dynamic Programming with Extra Space (O(m*n) time, O(m*n) space)

Dynamic programming removes repeated computation by storing results for each cell. Create a DP table where dp[i][j] represents the minimum cost to reach cell (i, j). Each cell depends only on the top and left neighbors, so the recurrence becomes dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Initialize the first row and first column because they have only one possible direction of movement. Iterate through the grid row by row to fill the table. This approach processes each cell exactly once, giving O(m*n) time and O(m*n) space.

Approach 3: Dynamic Programming with In-Place Modification (O(m*n) time, O(1) extra space)

The DP table is not strictly necessary because the grid itself can store the cumulative minimum cost. Start by updating the first row and first column with running sums since there is only one way to reach those cells. For the remaining cells, update the value using the same recurrence: grid[i][j] += min(grid[i-1][j], grid[i][j-1]). By the time you reach the bottom-right corner, it holds the minimum path sum. This approach still runs in O(m*n) time but reduces auxiliary space to O(1) since the input grid stores the DP state.

Problems like this are classic examples of grid-based dynamic programming. Each state depends on previously computed states in a structured traversal. The grid structure also makes it closely related to matrix traversal problems and common array DP patterns.

Recommended for interviews: Interviewers expect the dynamic programming solution. Starting with the recursive idea demonstrates understanding of the search space, but quickly optimizing it with DP shows you recognize overlapping subproblems. The in-place DP variant is typically considered the most polished solution because it achieves optimal O(m*n) time while keeping extra space at O(1).

Approach 1: Dynamic Programming with In-Place Modification

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.

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])

        return grid[m-1][n-1]

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    for(int i = 1; i < m; ++i) {
        grid[i][0] += grid[i-1][0];
    }
    for(int j = 1; j < n; ++j) {
        grid[0][j] += grid[0][j-1];
    }

    for(int i = 1; i < m; ++i) {
        for(int j = 1; j < n; ++j) {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[m-1][n-1];
}

JavaScript

var minPathSum = function(grid) {
    let m = grid.length;
    let n = grid[0].length;

    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0];
    }
    for (let j = 1; j < n; j++) {
        grid[0][j] += grid[0][j - 1];
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    return grid[m - 1][n - 1];
};

#include <stdio.h>

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    for(int i = 1; i < gridSize; ++i) {
        grid[i][0] += grid[i-1][0];
    }
    for(int j = 1; j < gridColSize[0]; ++j) {
        grid[0][j] += grid[0][j-1];
    }

    for(int i = 1; i < gridSize; ++i) {
        for(int j = 1; j < gridColSize[i]; ++j) {
            grid[i][j] += (grid[i-1][j] < grid[i][j-1] ? grid[i-1][j] : grid[i][j-1]);
        }
    }

    return grid[gridSize-1][gridColSize[gridSize-1]-1];
}

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.Min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

The Python code solves the problem by updating the grid in place to reflect the minimum path sum to each cell. It uses list slicing and loops to compute the results.

Complexity

Time Complexity: O(m * n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Dynamic Programming with Extra Space

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.

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

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

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

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

C++

#include <vector>
#include <algorithm>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));

    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

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

JavaScript

var minPathSum = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    let dp = Array.from(Array(m), () => Array(n).fill(0));

    dp[0][0] = grid[0][0];
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

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

#include <stdio.h>
#include <stdlib.h>

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int** dp = (int**)malloc(gridSize * sizeof(int*));
    for (int i = 0; i < gridSize; i++) {
        dp[i] = (int*)malloc(gridColSize[i] * sizeof(int));
    }

    dp[0][0] = grid[0][0];
    for (int i = 1; i < gridSize; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for (int j = 1; j < gridColSize[0]; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    for (int i = 1; i < gridSize; i++) {
        for (int j = 1; j < gridColSize[i]; j++) {
            dp[i][j] = grid[i][j] + (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
        }
    }

    int result = dp[gridSize - 1][gridColSize[gridSize - 1] - 1];

    for (int i = 0; i < gridSize; i++) free(dp[i]);
    free(dp);

    return result;
}

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++) {
            dp[i] = new int[n];
        }

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.Min(dp[i-1][j], dp[i][j-1]);
            }
        }

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

The Python code uses list comprehensions to create an auxiliary DP array, which holds intermediate results and calculates the result by tracking the minimum path sum.

Complexity

Time Complexity: O(m * n).
Space Complexity: O(m * n).

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] to represent the minimum path sum from the top left corner to (i, j). Initially, f[0][0] = grid[0][0], and the answer is f[m - 1][n - 1].

Consider f[i][j]:

If j = 0, then f[i][j] = f[i - 1][j] + grid[i][j];
If i = 0, then f[i][j] = f[i][j - 1] + grid[i][j];
If i > 0 and j > 0, then f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j].

Finally, return f[m - 1][n - 1].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

TypeScript

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const f: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(0));
    f[0][0] = grid[0][0];
    for (let i = 1; i < m; ++i) {
        f[i][0] = f[i - 1][0] + grid[i][0];
    }
    for (let j = 1; j < n; ++j) {
        f[0][j] = f[0][j - 1] + grid[0][j];
    }
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
        }
    }
    return f[m - 1][n - 1];
}

func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	f[0][0] = grid[0][0]
	for i := 1; i < m; i++ {
		f[i][0] = f[i-1][0] + grid[i][0]
	}
	for j := 1; j < n; j++ {
		f[0][j] = f[0][j-1] + grid[0][j]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]
		}
	}
	return f[m-1][n-1]
}

Rust

impl Solution {
    pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        for i in 1..m {
            grid[i][0] += grid[i - 1][0];
        }
        for i in 1..n {
            grid[0][i] += grid[0][i - 1];
        }
        for i in 1..m {
            for j in 1..n {
                grid[i][j] += grid[i][j - 1].min(grid[i - 1][j]);
            }
        }
        grid[m - 1][n - 1]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with In-Place Modification	Time Complexity: O(m * n). Space Complexity: O(1).
Dynamic Programming with Extra Space	Time Complexity: O(m * n). Space Complexity: O(m * n).
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Exploration	O(2^(m+n))	O(m+n)	Conceptual starting point to understand all possible paths
Dynamic Programming (Extra 2D Table)	O(m*n)	O(m*n)	Clear and easy implementation when modifying the input grid is not allowed
Dynamic Programming (In-Place Grid Update)	O(m*n)	O(1)	Optimal interview solution when the grid can be reused to store DP values

Frequently asked questions

Is Minimum Path Sum easy or hard?

Minimum Path Sum is considered a medium-level problem. The grid traversal idea is straightforward, but recognizing the dynamic programming recurrence and optimizing space are the key steps that elevate it beyond an easy problem.

Minimum Path Sum Python/Java solution

Most implementations use dynamic programming with nested loops over the grid. Python, Java, C++, and JavaScript solutions all follow the same recurrence: grid[i][j] + min(top, left), resulting in O(m*n) time complexity.

How to solve Minimum Path Sum in O(n)?

The problem can be solved in O(m*n) time with O(n) or O(1) extra space. Using a rolling array or modifying the grid directly removes the need for a full DP table while still computing the minimum cost for each cell.

What is the best approach for Minimum Path Sum?

Dynamic programming is the best approach. Each cell depends only on the minimum path sum from the top or left neighbor, so you compute results iteratively across the grid. The optimal implementation runs in O(m*n) time and can be reduced to O(1) extra space by updating the grid in place.

Is Minimum Path Sum asked at Google/Amazon/Meta?

Minimum Path Sum and similar grid DP problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers use it to evaluate dynamic programming fundamentals and the ability to optimize space usage.

What data structure is used in Minimum Path Sum?

The solution uses a 2D grid or DP table to store intermediate results. Each cell represents the minimum cost required to reach that position from the starting cell, forming a classic dynamic programming state table.

What is the time complexity of Minimum Path Sum?

The optimal dynamic programming solution runs in O(m*n) time because every grid cell is processed exactly once. Each computation only checks two neighboring cells, making the transition constant time.

Minimum Path Sum solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with In-Place Modification

Approach 2: Dynamic Programming with Extra Space

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Path Sum solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with In-Place Modification

Approach 2: Dynamic Programming with Extra Space

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems