My accepted Java solution, easy to understand !

  • 0

    public class Solution{

      publicint minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null) return 0;
        int len = triangle.size();
        int[] values = new int[len];  //only O(n) extra space
        values[0] = triangle.get(0).get(0);
        for(int i=1; i<len; i++){
        	List<Integer> cur = triangle.get(i);
        	for(int j=cur.size()-1; j>=0; j--){
        		if(j == 0){
        			values[j] = values[j] + cur.get(j);
        		}else if(j == cur.size()-1){
        			values[j] = values[j-1] + cur.get(j);
        			values[j] = (values[j] > values[j-1]? values[j-1]:values[j]) + cur.get(j);
        return values[0];


  • 0

    Mine is almost the same except the last step. I use for loop to find the min value rather than sort(). I think sort takes O(nlogn) which is longer than for loop.

Log in to reply

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