# Can I modify the triangle?

• If I am allowed to modify the triangle, I can do it in place, better than O(n).
below is my code.

``````public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
int n = triangle.size();
if (n == 0){
return 0;
}
ArrayList<Integer> lastRow = triangle.get(0);//last row we proceed.
for(int rowNum = 2; rowNum <= n; rowNum++ ){//the row number;
ArrayList<Integer> row = triangle.get(rowNum-1);
for (int col = 1; col <= rowNum; col++){
int topLeft = col-1 >= 1 ? lastRow.get(col-2) : Integer.MAX_VALUE;
int top = col <= rowNum-1 ? lastRow.get(col-1) : Integer.MAX_VALUE;
int min = getMinOf(topLeft, top)+row.get(col-1);
row.set(col-1, min);
}
lastRow = row;
}
return minValueOf(triangle.get(n-1));
}

private int getMinOf(int value1, int value2){
return value1<value2 ? value1:value2;
}

private int minValueOf(ArrayList<Integer> list){
if (list.size() == 0){
return 0;
}
int min = list.get(0);
for(int v : list){
if (v < min){
min = v;
}
}
return min;
}``````

• No, you cannot.

PS: Do you know `Math.min()`? And can you do it without scanning the last row?

• Actually you can. This solution is accepted.

``````class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
"""Think about the triangle as a graph similar to a tree,
with nodes as the numbers in the triangle, and edges connecting
to "adjacent" numbers. From top down, we may treat their
relationship as parents and children, where some nodes can have
two parents, such as 5 in the given example (it has 3 and 4 as
parents).

Starting from the second level (the level with 2 elements),
computes the min value it could be at triangle[i][j] by
- add up triangle[i][j] with it's parents, respectively
- get the min value of two sums
and then replace triangle[i][j] with the min value.
(for triangle[i][j], its parents could be triangle[i-1][j-1],
and triangle[i-1][j]; while sometimes there is only one parent)

By interatively doing this, the parents hold the sum of min
path from them up to the "root" element.
"""
if triangle is None or len(triangle) == 0:
return

if len(triangle) == 1:
return triangle[0][0]

for level in xrange(1, len(triangle)):
# current level to update the sum of min path
cur_level = triangle[level]
upper_level = triangle[level - 1]

for index in xrange(len(cur_level)):

# for left most number of each level, it has no left
# parent, so the sum is only to add with righ parent
if index == 0:
cur_level[index] += upper_level[0]

# for right most number of each level, it has no right
# parent, so the sum is only to add with left parent
elif index == len(upper_level):
cur_level[index] += upper_level[index - 1]

# otherwise, there are two parents
else:
cur_level[index] = min(
cur_level[index] + upper_level[index - 1],
cur_level[index] + upper_level[index]
)

# the last level eventually holds min values of all paths
return min(triangle[-1])``````

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