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

  • 4

    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++){
            for(int i=height-1;i>0;i--){
                for(int j=0;j<i;j++){
            return mins[0];

  • 0

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

  • 0

    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.