Freedom Day Special: 85% OFF on .NET AI & Architect Career
Ends in
00d
00h
00m
00s
 Get Now
Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Minimum Path Sum

Medium Acceptance 50.00% Points 30.00

Given a n 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.

Examples
Example 1

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

Example 2

Input: grid = [[1,2],[4,5]]

Output: 8

Explanation: Because the path 1 -> 2 -> 5 minimizes the sum.

Hints
Hint 1
Expected Time Complexity: O(n^2)
Hint 2
Expected Auxiliary Space: O(n^2)
Constraints
  • n == grid.length, grid[i].length
  • 1 <= n <= 200
  • 0 <= grid[i][j] <= 200
Companies
Amazon Microsoft Samsung Goldman Sachs
Topics
Array Dynamic Programming 2D Array
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions