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.

Description Solution Video 14:06

64. Minimum Path Sum

Medium68.6% acceptance17 companies

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

Asked at 17 companies

Texas Instruments Spacex Goldman Sachs

Infosys Squarepoint Capital Waymo General Motors Amazon Microsoft Tiktok Zoho NVIDIA

+5 more

Snapchat

Google Meta Bloomberg Uber

Topics

14:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

64. Minimum Path Sum

Asked at 17 companies

Topics

Similar problems