Triangle - Array - Medium - LeetCode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

public class Solution {
 public int MinimumTotal(IList<IList<int>> triangle) {
 int rows = triangle.Count();
 
 for(int i=1;i<rows;i++){
 for(int j=0;j<triangle[i].Count();j++){
 if(j==0 || j == triangle[i].Count()-1){
 if(j > triangle[i-1].Count()-1){
 triangle[i][j]+=triangle[i-1][j-1];
 }
 else{
 triangle[i][j]+=triangle[i-1][j];
 } 
 }
 else{
 triangle[i][j] += Math.Min(triangle[i-1][j-1], triangle[i-1][j]);
 }
 }
 
 }
 
 int min = int.MaxValue;
 
 for(int i=0;i<triangle[rows-1].Count();i++){
 min = Math.Min(min, triangle[rows-1][i]);
 }
 
 return min;
 } 
}

Time Complexity: O(m*n)

Space Complexity: O(1)