public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if (triangle == null  triangle.size() < 1) {
return 0;
}
int size = triangle.size();
for (int i = size  2; i >= 0; i) {
ArrayList<Integer> nextLine = triangle.get(i + 1);
ArrayList<Integer> nowLine = triangle.get(i);
for (int j = 0; j <= i; j++) {
nowLine.set(j, nowLine.get(j) + Math.min(nextLine.get(j), nextLine.get(j + 1)));
}
}
return triangle.get(0).get(0);
}
Is it O(1) extra space?


You technically have solved it, but you do realize that your algorithm changes the Triangle passed in (and therefore the one outside the method), right? So long as you are fine with that, yes, that solution works, and can be considered O(1), or without extra space, but just remember that methods usually only return a value or change the values of a data structure, not both.
The challenge using O(n) is solved using the same idea, but does it in a way that does not change the Triangle itself. See if you can solve it that way as well.

Similar idea, but without modify the original input. An extra array used instead of two arrays in your implementation. O(n) extra space in my case.
class Solution { // maintain an array of minimum sums to current level in a bottomup manner public: int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()  triangle[0].empty() ) return 0; int l = triangle.size(); // iteration + topdown vector<int> level_sums(triangle[l1]); for (int i = l2; i >= 0; i) { for (int j = 0; j < i+1; j++) { // new sum at [i][j] is the value at [i][j] + min(level_sum[i+1][j], level_sum[i+1][j+1]) level_sums[j] = triangle[i][j] + min(level_sums[j], level_sums[j+1]); } } return level_sums[0]; } };