# Java O(n^2) runtime O(1) space

• The minimum sum from root to triangle[i][j] can only come from triangle[i - 1][j - 1] and triangle[i - 1][j]
so store the minimum sum to the original list to save memory

``````public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0)
return 0;
int sum;
int min;
int n = triangle.size();
for (int i = 1; i <= n - 1; i++) {
min = triangle.get(i - 1).get(0);
sum = triangle.get(i).get(0) + min;
triangle.get(i).set(0, sum);
for (int j = 1; j <= i - 1; j++) {
min = Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j));
sum = triangle.get(i).get(j) + min;
triangle.get(i).set(j, sum);
}
min = triangle.get(i - 1).get(i - 1);
sum = triangle.get(i).get(i) + min;
triangle.get(i).set(i, sum);
}
min = triangle.get(n - 1).get(0);
for (int j = 1; j < n; j++)
min = Math.min(min, triangle.get(n - 1).get(j));
return min;
}
}``````

• Horrible choice of method signature makes handling it really unreadable, it should've been `int[][]` as each `triangle[i]` can have different lengths... Here's a more readable version via extracting `triangle.get(x)`:

``````public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0)
return 0;
int n = triangle.size();
int min, sum;
for (int i = 1; i < n; i++) {
List<Integer> prevRow = triangle.get(i - 1);
List<Integer> thisRow = triangle.get(i);
min = prevRow.get(0);
sum = thisRow.get(0) + min;
thisRow.set(0, sum);
for (int j = 1; j <= i - 1; j++) {
min = Math.min(prevRow.get(j - 1), prevRow.get(j));
sum = thisRow.get(j) + min;
thisRow.set(j, sum);
}
min = prevRow.get(i - 1);
sum = thisRow.get(i) + min;
thisRow.set(i, sum);
}
min = Integer.MAX_VALUE;
for (int cost : triangle.get(n - 1))
min = Math.min(min, cost);
return min;
}``````

• smart idea, but set() may cost more time

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