// 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.

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null || triangle.size() == 0) return 0;

        int level = triangle.size();

        for(int i = 1; i < level; i++){
        	List<Integer> previous = triangle.get(i - 1);
        	List<Integer> current = triangle.get(i);

        	for(int j = 0; j < current.size(); j++){
        		if(j == 0){
        			current.set(j, previous.get(0) + current.get(j));
        		}else if(j == current.size() - 1){
        			current.set(j, current.get(j) + previous.get(previous.size() - 1));
        		}else{
	        		int left = previous.get(j - 1);
	        		int right = previous.get(j);

	        		current.set(j, left > right? right + current.get(j) : left + current.get(j));	
        		}
        	}
        }

        int min = Integer.MAX_VALUE;

        for(int i : triangle.get(level - 1)){
        	min = min > i? i : min;
        }

        return min;
    }
}
@@ -446,16 +446,59 @@
 angle.%0A%0A
+%0A// Space : O(2n * n) --%3E O(n2) space.%0A%0A// 
 public c
@@ -513,16 +513,19 @@
 ution %7B%0A
+// 
     publ
@@ -576,16 +576,19 @@
 ngle) %7B%0A
+// 
         
@@ -643,16 +643,19 @@
 urn 0;%0A%0A
+// 
         
@@ -680,24 +680,27 @@
 le.size();%0A%0A
+// 
         for(
@@ -723,24 +723,27 @@
 evel; i++)%7B%0A
+// 
         %09Lis
@@ -785,16 +785,19 @@
 i - 1);%0A
+// 
         
@@ -839,16 +839,19 @@
 et(i);%0A%0A
+// 
         
@@ -892,24 +892,26 @@
 ; j++)%7B%0A
+//
         
 %09%09if(j =
@@ -902,16 +902,17 @@
         
+ 
 %09%09if(j =
@@ -917,16 +917,19 @@
  == 0)%7B%0A
+// 
         
@@ -977,32 +977,34 @@
 nt.get(j));%0A
+//
         
 %09%09%7Delse if(j
@@ -987,24 +987,25 @@
 ;%0A//        
+ 
 %09%09%7Delse if(j
@@ -1029,16 +1029,19 @@
 ) - 1)%7B%0A
+// 
         
@@ -1111,16 +1111,19 @@
  - 1));%0A
+// 
         
@@ -1131,16 +1131,19 @@
 %09%7Delse%7B%0A
+// 
 %09       
@@ -1177,16 +1177,19 @@
 j - 1);%0A
+// 
 %09       
@@ -1221,16 +1221,19 @@
 et(j);%0A%0A
+// 
 %09       
@@ -1314,16 +1314,19 @@
 t(j));%09%0A
+// 
         
@@ -1329,24 +1329,26 @@
     %09%09%7D%0A
+//
         
 %09%7D%0A     
@@ -1339,19 +1339,23 @@
         
+ 
 %09%7D%0A
+// 
         
@@ -1349,32 +1349,35 @@
 %7D%0A//         %7D%0A%0A
+// 
         int min 
@@ -1398,16 +1398,19 @@
 VALUE;%0A%0A
+// 
         
@@ -1447,16 +1447,19 @@
  - 1))%7B%0A
+// 
         
@@ -1479,24 +1479,27 @@
 i? i : min;%0A
+// 
         %7D%0A%0A 
@@ -1497,16 +1497,19 @@
      %7D%0A%0A
+// 
         
@@ -1520,15 +1520,597 @@
 rn min;%0A
+//     %7D%0A// %7D%0A%0Apublic class Solution %7B%0A    public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A        if(triangle == null %7C%7C triangle.size() == 0)%7B%0A            return 0;%0A        %7D%0A        %0A        int len = triangle.size();%0A        List%3CInteger%3E min = triangle.get(triangle.size() - 1);%0A        %0A        for(int i = len - 2; i %3E= 0; i--)%7B%0A            for(int j = 0; j %3C= i; j++)%7B%0A                min.set(j, min.get(j) %3C min.get(j + 1)? triangle.get(i).get(j) + min.get(j) : triangle.get(i).get(j) + min.get(j + 1)); %0A            %7D%0A        %7D%0A        %0A        return min.get(0);%0A
     %7D%0A%7D

update triangle solution using o(n) space. bottom-up approach