# My 8 line DP Java code(4 meaningful lines) with O(1) space

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

The idea is simple.

1. Go from bottom to top.

2. We start form the row above the bottom row [size()-2].

3. Each number add the smaller number of two numbers that below it.

4. And finally we get to the top we the smallest sum.

• you modified the original array. it may be inappropriate

• +1 for should not modify the original array. But that could be solved simply clone a list.

• My C++ version of your algorithm. I hope it's easier to read.

``````int minimumTotal(vector<vector<int> > &triangle) {
for (int i=triangle.size()-2; i>=0; --i){
for (int j=0; j<triangle[i].size(); ++j){
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
}
return triangle[0][0];
}``````

• What if the List is LinkedList? What is the complexity of the get function ?

• Awesome approach !

• Why cannot the original array be modified?

• I see this solution only beats 8.41% of java solutions. But I can't figure out why this concise solution is slow. Any idea?

• it's O(n), if it's linked list, I think we should better use iterator to traverse every layer, otherwise using get/set the time complexity would be terrible

• @zizizi You surely can modify it, but it's just not a good coding style. Because it may cause some mistakes in certain cases.

• Why does my code fail for inputs [[-1],[2,3],[1,-1,-3]].The output which I get is -2 while the expected output is -1 ,but -2 is less than -1 so shouldnt that be the answer

• @lihao814386741 For people asking "what if get(i) takes some time"? Then just store the intermediate results.

``````public class Solution {
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {

List<Integer> previousRow = triangle.get(triangle.size()-1);
for(int i = triangle.size()-2; i>=0; i--){
List<Integer> currentRow = triangle.get(i);
int previousElem = previousRow.get(0);
for(int j = 0; j<currentRow.size(); j++){
currentRow.set(j, currentRow.get(j) + Math.min(previousElem, previousElem = previousRow.get(j+1)));
}
previousRow = currentRow;
}

return triangle.get(0).get(0);
}
}
``````

If it's a linked list you can also use iterators.

• @hpplayer here is a way to avoid modifying the input, C#

``````    public int MinimumTotal(IList<IList<int>> triangle)
{
int[] row = triangle[triangle.Count - 1].ToArray();

for (int level = triangle.Count - 2; level >= 0; level--)
{
int[] nextRow = new int[triangle[level].Count];
for (int i = 0; i < triangle[level].Count; i++)
{
nextRow[i] = triangle[level][i] + Math.Min(row[i], row[i+1]);
}
row = nextRow;
}

return row[0];
}
``````

• `for(int j = 0; j <= i; j++)` is less illustrative than `for(int j = 0; j <= triangle.get(i).size(); j++)`, while, in fact, `i == triangle.get(i).size()` in this case/problem.

• Java code not modifying the original list, but using a list copied from last row in the triangle.

``````public int minimumTotal(List<List<Integer>> list) {
int n = list.size();
List<Integer> li = new ArrayList<>(list.get(n-1));
for(int i=n-2; i>=0; i--){
for(int j=0; j<=i; j++){
li.set(j, list.get(i).get(j) + Math.min( li.get(j), li.get(j+1) ));
}
}
return li.get(0);
}
``````

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