My Java version solution with O(n) space Accepted


  • 3
    Y

    row by row from bottom to the up top, calculate the minimum value to each point.
    we just use one array to "remember" what is the minimum total value to each point from bottom.

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

  • 0
    Z

    If you can modify the triangle your solution is even simplier:

    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            for(int i = triangle.size() - 2; i >= 0; --i) {
                List<Integer> prevRow = triangle.get(i + 1);
                List<Integer> row = triangle.get(i);
                for(int j = 0; j < row.size(); ++j) {
                    int newValue = row.get(j) + Math.min(prevRow.get(j), prevRow.get(j + 1));
                    row.set(j, newValue);
                }
            }
    
            return triangle.get(0).get(0);
        }
    }
    

    And you don't need to do the following:
    for(int i=0; i<rows+1; i++)
    a[i] = 0;
    JVM does it for you.


  • 0
    M

    except that's not O(n) solution, because you are modifying input array.


  • 0
    M

    great solution!


  • 0
    L

    But the question says "n is the total number of rows in the triangle."
    It seems to me that it is a O(n^2) solution rather than O(n)...


Log in to reply
 

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