C++ solution with O(1) extra space - 6ms


  • 0
    S

    The idea is to go from second last row and keep on updating the min values for each element of that row

     int minimumTotal(vector<vector<int>>& triangle) {
            for(int i=triangle.size()-2;i>=0;i--){
                for(int j=0;j<triangle[i].size();j++){
                    triangle[i][j]=triangle[i][j]+min(triangle[i+1][j],triangle[i+1][j+1]);
                }
            }
            return triangle[0][0];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.