# O(n) Space Java Simple Solution

• ``````public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for(int i=1;i<triangle.size();i++){
ArrayList<Integer> curlist=(ArrayList<Integer>)triangle.get(i);
for(int j=0;j<curlist.size();j++){
if(j==0)curlist.set(j,triangle.get(i-1).get(j)+curlist.get(j));
else if(j==curlist.size()-1)curlist.set(j,triangle.get(i-1).get(j-1)+curlist.get(j));
else{
int sum1=triangle.get(i-1).get(j-1)+curlist.get(j);
int sum2=triangle.get(i-1).get(j)+curlist.get(j);
curlist.set(j,sum1<sum2?sum1:sum2);
}
}

}
List<Integer> last=triangle.get(triangle.size()-1);
int sum=Integer.MAX_VALUE;
for(int i:last){
if(i<sum)sum=i;
}
return sum;
}
}``````

• The same as my first version. But I noticed an faster way which is calculate from bottom to top to avoid get the smallest from the array.

``````public int minimumTotal3(List<List<Integer>> triangle) {
int i1, i2;
int[] arr = new int[triangle.get(triangle.size() - 1).size() + 1];

for (int i = triangle.size() - 1; i >= 0; --i) {
List<Integer> array = triangle.get(i);
for (int j = 0; j < array.size(); j++) {
i1 = arr[j] + array.get(j);
i2 = arr[j + 1] + array.get(j);
arr[j] = i1 > i2 ? i2: i1;
}
}

return arr[0];
}``````

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