Is it O(1) extra space?


  • 0
    Z
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null || triangle.size() < 1) {
        	return 0;
        }
        
        int size = triangle.size();
        
        for (int i = size - 2; i >= 0; i--) {
        	ArrayList<Integer> nextLine = triangle.get(i + 1);
    		ArrayList<Integer> nowLine = triangle.get(i);
        	for (int j = 0; j <= i; j++) {
        		nowLine.set(j, nowLine.get(j) + Math.min(nextLine.get(j), nextLine.get(j + 1)));
        	}
        }
        
        return triangle.get(0).get(0);        
    }

  • 3
    M

    You technically have solved it, but you do realize that your algorithm changes the Triangle passed in (and therefore the one outside the method), right? So long as you are fine with that, yes, that solution works, and can be considered O(1), or without extra space, but just remember that methods usually only return a value or change the values of a data structure, not both.

    The challenge using O(n) is solved using the same idea, but does it in a way that does not change the Triangle itself. See if you can solve it that way as well.


  • 0
    Z

    3ks for your advice


  • 0
    S

    Similar idea, but without modify the original input. An extra array used instead of two arrays in your implementation. O(n) extra space in my case.

    class Solution { // maintain an array of minimum sums to current level in a bottom-up manner
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            if (triangle.empty() || triangle[0].empty() )
                return 0;
                
            int l = triangle.size();
            // iteration + top-down
            vector<int> level_sums(triangle[l-1]);
            for (int i = l-2; i >= 0; i--) {
                for (int j = 0; j < i+1; j++) {
                    // new sum at [i][j] is the value at [i][j] + min(level_sum[i+1][j], level_sum[i+1][j+1])
                    level_sums[j] = triangle[i][j] + min(level_sums[j], level_sums[j+1]);
                }
            } 
            return level_sums[0];
        }
    };

  • -1
    L
    class Solution {
    public:
    //bottom - top
    int minimumTotal(vector<vector<int> > &triangle) {
    	int i,j;
    	int m = triangle.size();
    	for(i=m-2;i>=0;i--){
    		int n=triangle[i].size();
    		for(j=0;j<n;j++){
    			triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);
    		}
    	}
    	return triangle[0][0];
    }
    };`    

Log in to reply
 

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