Skip to main content
Talentd

Minimum Path Sum - Solution & Explanation

MediumArrayDynamic ProgrammingMatrix23 min readAsked at: Amazon, Microsoft, Goldman Sachs +14
Practice this problem

Problem Statement

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the additional 2D array used.

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) as we modify the grid in place.

Dynamic Programming with Extra Space

Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the additional 2D array used.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ExplorationO(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

Video Solution

Minimum path sum | Min cost Path | Dynamic programming | Leetcode #64 • Techdose • 89,144 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Path Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if There is a Path With Equal Number of 0's And 1's

Next

Cherry Pickup