Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

172. Minimum Path Sum

MediumDay 51 of 60Dynamic Programming

Given an m x n grid of non-negative numbers, find a path from the top-left to the bottom-right cell that minimises the sum of all numbers on it, moving only right or down. Return that minimum sum.

Example 1
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
The path 1, 3, 1, 1, 1 sums to 7.
Example 2
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
Hints
Frequently asked at: Amazon, Google, Goldman Sachs
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min