Simple 3ms Java Solution, O(N) space, without modifying the input


  • 0
    Y
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null||triangle.size()==0) return 0;
        int size = triangle.size();
        int result[] = new int[triangle.size()];
        List<Integer> temp = triangle.get(size-1);
        int length = temp.size();
        for(int i=0;i<length;i++){result[i]=temp.get(i);}
        for(int i=size-2;i>=0;i--){
            length=triangle.get(i).size();
            temp = triangle.get(i);
            for(int j=0;j<length;j++)
                result[j]=Math.min(result[j],result[j+1])+temp.get(j);
        }
        return result[0];
    }

Log in to reply
 

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