64. Minimum Path Sum
Minimum Path Sum (LeetCode 64) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
How to solve Minimum Path Sum
Minimum Path Sum is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.
Work towards the solution in these steps:
- Consider using dynamic programming since the problem involves making optimal choices at each step to minimize a cumulative value.
- Think about how to represent the problem state: what information do you need at each cell to determine the minimum path sum to that point?
- Try to build a DP table where each cell stores the minimum path sum to reach that cell from the start, using only moves from the left or above.
The reference solution runs in O(m * n) time and O(1) space.
The Minimum Path Sum solution and editorial walks through the full approach with reference code.
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
Topics and companies
Topics: Array, Dynamic Programming, Matrix.
Reported in interviews at Google, Amazon, Goldman Sachs, Facebook, Apple, Snapchat, Tesla.
How to practise Minimum Path Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(1) space.
Open Minimum Path Sum in the code editor, or read the Minimum Path Sum editorial for a worked solution with its approach and complexity analysis.
Where Minimum Path Sum sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Unique Paths on Grid) subpattern
- The full DSA patterns sheet
Problems related to Minimum Path Sum
Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:
- Count Square Submatrices with All Ones — Medium, same subpattern
- Interleaving String — Medium, same subpattern
- Longest Increasing Path in a Matrix — Hard, same subpattern
- Maximal Square — Medium, same subpattern
- Minimum Falling Path Sum — Medium, same subpattern
- Triangle — Medium, same subpattern
Minimum Path Sum FAQ
What is the LeetCode number of Minimum Path Sum?
Minimum Path Sum is LeetCode problem 64, rated Medium.
What pattern is used to solve Minimum Path Sum?
Minimum Path Sum is a Unique Paths on Grid problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
What is the time complexity of Minimum Path Sum?
The reference solution runs in O(m * n) time and O(1) space.
Which companies ask Minimum Path Sum?
Minimum Path Sum has been reported in interviews at Google, Amazon, Goldman Sachs, Facebook, Apple, Snapchat, Tesla.