Minimum Path Sum
Updated
Problem statement
You are given an m x n grid of non-negative integers. A path starts at the top-left cell (0, 0), ends at the bottom-right cell (m - 1, n - 1), and moves one cell at a time, either right or down.
The cost of a path is the sum of the values of all cells it visits, including the first and the last cell. Return the smallest possible cost.
Function
minPathSum(grid: int[][]) → intExamples
Example 1
grid = [[1,4,2],[3,1,6],[5,2,1]]return = 8The path down, right, down, right visits 1, 3, 1, 2, 1, for a sum of 8. Every other path costs more; for example, going right along the top row and then down the last column visits 1, 4, 2, 6, 1, a sum of 14.
Example 2
grid = [[2,9,0,0],[1,1,8,1]]return = 12Going down first looks cheaper (1 is smaller than 9), but that path, 2, 1, 1, 8, 1, has to cross the 8 and sums to 13. Paying for the 9 right away leads to the 0s: 2, 9, 0, 0, 1 sums to 12, the minimum.
Constraints
m == grid.length,n == grid[i].length, and1 <= m, n <= 2000 <= grid[i][j] <= 1000
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Maximum All-Ones Square Side LengthOmnissa · ONSITE INTERVIEWOmnissa interview questions
- Minimum Path SumAmazon · ONSITE INTERVIEW
- Minimum Path SumBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Bomb Enemy Best CoordinatesSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions
- Largest Square of Ones in a GridExpedia · ONSITE INTERVIEWExpedia interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
- Maximal Rectangle in a Binary MatrixGoogle · ONSITE INTERVIEWGoogle interview questions
- Find Robots by Blocker DistancesUber · PHONE SCREENUber interview questions
- Largest Square of OnesOpenAI · OAOpenAI interview questions