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

• 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;
}
};``````

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