Java O(n^2) runtime O(1) space


  • 2

    The minimum sum from root to triangle[i][j] can only come from triangle[i - 1][j - 1] and triangle[i - 1][j]
    so store the minimum sum to the original list to save memory

    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0)
                return 0;
            int sum;
            int min;
            int n = triangle.size();
            for (int i = 1; i <= n - 1; i++) {
                min = triangle.get(i - 1).get(0);
                sum = triangle.get(i).get(0) + min;
                triangle.get(i).set(0, sum);
                for (int j = 1; j <= i - 1; j++) {
                    min = Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j));
                    sum = triangle.get(i).get(j) + min;
                    triangle.get(i).set(j, sum);
                }
                min = triangle.get(i - 1).get(i - 1);
                sum = triangle.get(i).get(i) + min;
                triangle.get(i).set(i, sum);
            }
            min = triangle.get(n - 1).get(0);
            for (int j = 1; j < n; j++)
                min = Math.min(min, triangle.get(n - 1).get(j));
            return min;
        }
    }

  • 0
    T

    Horrible choice of method signature makes handling it really unreadable, it should've been int[][] as each triangle[i] can have different lengths... Here's a more readable version via extracting triangle.get(x):

    public int minimumTotal(List<List<Integer>> triangle) {
    	if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0)
    		return 0;
    	int n = triangle.size();
    	int min, sum;
    	for (int i = 1; i < n; i++) {
    		List<Integer> prevRow = triangle.get(i - 1);
    		List<Integer> thisRow = triangle.get(i);
    		min = prevRow.get(0);
    		sum = thisRow.get(0) + min;
    		thisRow.set(0, sum);
    		for (int j = 1; j <= i - 1; j++) {
    			min = Math.min(prevRow.get(j - 1), prevRow.get(j));
    			sum = thisRow.get(j) + min;
    			thisRow.set(j, sum);
    		}
    		min = prevRow.get(i - 1);
    		sum = thisRow.get(i) + min;
    		thisRow.set(i, sum);
    	}
    	min = Integer.MAX_VALUE;
    	for (int cost : triangle.get(n - 1))
    		min = Math.min(min, cost);
    	return min;
    }

  • 0
    L

    smart idea, but set() may cost more time


Log in to reply
 

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