[Solved] 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.

Question

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:

Machine Learning Projects
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] <= 100

Python Solution

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid[0])
        n = len(grid)

        for i in range (1,n):
            grid[i][0] = grid[i][0] + grid[i-1][0]

        for i in range(1,m):
            grid[0][i] = grid[0][i] + grid[0][i-1]

        for i in range (1,n):
            for j in range (1,m):
                grid[i][j] = min(grid[i][j] + grid[i-1][j] , grid[i][j] + grid[i][j-1])

        return grid[-1][-1]
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 514

Leave a Reply

Your email address will not be published. Required fields are marked *