O(n^2) time O(n) space java dp solution


  • 4
    J

    This bottom-up solution uses the array mins[] to store the minimum sum
    of each path until the current number.

    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle==null||triangle.isEmpty()) return 0;
            final int height=triangle.size();
            int[] mins = new int[height];
            for(int i=0;i<height;i++){
                mins[i]=triangle.get(height-1).get(i);
            }
            
            for(int i=height-1;i>0;i--){
                for(int j=0;j<i;j++){
                    mins[j]=Math.min(mins[j+1],mins[j])+triangle.get(i-1).get(j);
                }
            }
            return mins[0];
        }
     
    }

  • 0
    W

    why O(nlogn) time? The nested for-loops are O(n^2)


  • 0
    G

    good one, but it is not O(nlogn). It is at least O(n^2) depends on if the list is an ArrayList. If the list is a LinkedList instead, it would be O(n^3) time.


Log in to reply
 

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