My 12ms concise c++ solution with O(n) extra space


  • 0
    V

    class Solution {

    public:

    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()){
            return 0;
        }
        int size = triangle.size();
        vector<int> sum(triangle[size-1]);     // O(n) extra space
        for(int i = size-2; i > -1; i--){               // sum from bottom to top
            for(int j = 0; j < size; j++){
                sum[j] = min(sum[j], sum[j+1]) + triangle[i][j];   
            }
        }
        return sum[0];
    }
    

    };


Log in to reply
 

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