# Blogs Hub

### by Sumit Chourasia | Oct 31, 2020 | Category :coding | Tags : algorithmarraydata-structureleetcodemedium #### 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.Length;
var T = new int[r,c];
for(int i=0;i<r;i++){
if(i==0){
T[i,0]=grid[i];
}
else{
T[i,0]=grid[i] + T[i-1,0];
}
}

for(int i=0;i<c;i++){
if(i==0){
T[0,i] = grid[i];
}
else{
T[0,i] = grid[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)