My C++ solution with θ(n) time complexity and O(1) space complexity


  • 0
    G

    My solution simply uses input as my DP sources, so it should be constant amount of memory usage.
    Time complexity is θ(n), where n denotes the total number of elements in triangle.

    My codes should be very straight forward, which is just update current level according to last level.

    class Solution {
        public:
            int minimumTotal(vector<vector<int> > &triangle) {
                if (!triangle.size())       return 0;
                if (triangle.size() == 1)   return triangle[0][0];
                
                for (int i = 1; i < triangle.size(); i++) {
                    for (int j = 0; j < triangle[i].size(); j++) {
                        if (j == 0)         triangle[i][j] += triangle[i-1][j];
                        else if (j == i)    triangle[i][j] += triangle[i-1][j-1];
                        else                triangle[i][j] += triangle[i-1][j-1] > triangle[i-1][j] ?
                                                                triangle[i-1][j] : triangle[i-1][j-1];
                    }
                }
                
                int min = INT_MAX;
                for (int i = 0; i < triangle.back().size(); i++)
                    min = triangle.back()[i] > min ? min : triangle.back()[i];
                
                return min;
            }
        };

Log in to reply
 

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