O(n) Space Java Simple Solution


  • 0
    J
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            for(int i=1;i<triangle.size();i++){
                ArrayList<Integer> curlist=(ArrayList<Integer>)triangle.get(i);
                for(int j=0;j<curlist.size();j++){
                    if(j==0)curlist.set(j,triangle.get(i-1).get(j)+curlist.get(j));
                    else if(j==curlist.size()-1)curlist.set(j,triangle.get(i-1).get(j-1)+curlist.get(j));
                    else{
                        int sum1=triangle.get(i-1).get(j-1)+curlist.get(j);
                        int sum2=triangle.get(i-1).get(j)+curlist.get(j);
                        curlist.set(j,sum1<sum2?sum1:sum2);
                    }
                }
                
            }
            List<Integer> last=triangle.get(triangle.size()-1);
            int sum=Integer.MAX_VALUE;
            for(int i:last){
                if(i<sum)sum=i;
            }
            return sum;
        }
    }

  • 0
    P

    The same as my first version. But I noticed an faster way which is calculate from bottom to top to avoid get the smallest from the array.

    public int minimumTotal3(List<List<Integer>> triangle) {
        int i1, i2;
        int[] arr = new int[triangle.get(triangle.size() - 1).size() + 1];
    
        for (int i = triangle.size() - 1; i >= 0; --i) {
            List<Integer> array = triangle.get(i);
            for (int j = 0; j < array.size(); j++) {
                i1 = arr[j] + array.get(j);
                i2 = arr[j + 1] + array.get(j);
                arr[j] = i1 > i2 ? i2: i1;
            }
        }
    
        return arr[0];
    }

Log in to reply
 

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