Blogs Hub

by Sumit Chourasia | Oct 31, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Minimum Path Sum - Array - Medium - LeetCode

Minimum Path Sum - Array - Medium - LeetCode

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

public class Solution {
    public int MinPathSum(int[][] grid) {
        int r = grid.Length;
        int c = grid[0].Length;
        var T = new int[r,c];
        for(int i=0;i<r;i++){
            if(i==0){
                T[i,0]=grid[i][0];
            }
            else{
                T[i,0]=grid[i][0] + T[i-1,0];   
            }            
        }
        
        for(int i=0;i<c;i++){
            if(i==0){
                T[0,i] = grid[0][i];
            }
            else{
                T[0,i] = grid[0][i] + T[0,i-1];
            }
        }
        
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                T[i,j] = Math.Min(T[i-1,j],T[i,j-1]) + grid[i][j];
            }
        }
        
        return T[r-1,c-1];
    }
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Contributed By: Sumit Chourasia
Rotate String - String - Easy - LeetCode
Contributed By: Sumit Chourasia
Jump Game - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Sort Colors - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Decode XORed Array - Array - Easy - LeetCode