Leetcode: Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution:

O(n) extra space:

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) 
    {
        int [] minValue = new int[1];
        minValue[0] = triangle.size()>0 ? triangle.get(0).get(0) : 0;
        for(int i=1; i < triangle.size(); i++)
        {
            int[] temp = new int [i+1];
            for (int j=0; j<=i; j++)
            {
                temp[j] = j>0 ? minValue[j-1] : Integer.MAX_VALUE;
                temp[j] = j<i ? Math.min(minValue[j],temp[j]) : temp[j];
                temp[j] = temp[j] + triangle.get(i).get(j);
            }
            minValue=temp;
        }
        int min= minValue[0];
        for (int i=0; i<minValue.length; i++)
            min =minValue[i]<min ? minValue[i] : min;
        return min;
    }

O(1) extra space (using the input as temporary storage):

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<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);
    }
}