Can I modify the triangle?


  • 0
    Y

    If I am allowed to modify the triangle, I can do it in place, better than O(n).
    below is my code.

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int n = triangle.size();
        if (n == 0){
            return 0;
        }
        ArrayList<Integer> lastRow = triangle.get(0);//last row we proceed.
        for(int rowNum = 2; rowNum <= n; rowNum++ ){//the row number;
            ArrayList<Integer> row = triangle.get(rowNum-1);
            for (int col = 1; col <= rowNum; col++){
                int topLeft = col-1 >= 1 ? lastRow.get(col-2) : Integer.MAX_VALUE;
                int top = col <= rowNum-1 ? lastRow.get(col-1) : Integer.MAX_VALUE;
                int min = getMinOf(topLeft, top)+row.get(col-1);
                row.set(col-1, min);
            }
            lastRow = row;
        }
        return minValueOf(triangle.get(n-1));
    }
    
    private int getMinOf(int value1, int value2){
        return value1<value2 ? value1:value2;
    }
    
    private int minValueOf(ArrayList<Integer> list){
        if (list.size() == 0){
            return 0;
        }
        int min = list.get(0);
        for(int v : list){
            if (v < min){
                min = v;
            }
        }
        return min;
    }

  • 0
    L

    No, you cannot.

    PS: Do you know Math.min()? And can you do it without scanning the last row?


  • 1
    S

    Actually you can. This solution is accepted.

    class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        """Think about the triangle as a graph similar to a tree,
        with nodes as the numbers in the triangle, and edges connecting
        to "adjacent" numbers. From top down, we may treat their
        relationship as parents and children, where some nodes can have
        two parents, such as 5 in the given example (it has 3 and 4 as
        parents).
    
        Starting from the second level (the level with 2 elements),
        computes the min value it could be at triangle[i][j] by
         - add up triangle[i][j] with it's parents, respectively
         - get the min value of two sums
        and then replace triangle[i][j] with the min value.
        (for triangle[i][j], its parents could be triangle[i-1][j-1],
        and triangle[i-1][j]; while sometimes there is only one parent)
        
        By interatively doing this, the parents hold the sum of min
        path from them up to the "root" element.
        """
        if triangle is None or len(triangle) == 0:
            return
        
        if len(triangle) == 1:
            return triangle[0][0]
        
        for level in xrange(1, len(triangle)):
            # current level to update the sum of min path
            cur_level = triangle[level]
            upper_level = triangle[level - 1]
            
            for index in xrange(len(cur_level)):
                
                # for left most number of each level, it has no left
                # parent, so the sum is only to add with righ parent
                if index == 0:
                    cur_level[index] += upper_level[0]
                
                # for right most number of each level, it has no right
                # parent, so the sum is only to add with left parent
                elif index == len(upper_level):
                    cur_level[index] += upper_level[index - 1]
                
                # otherwise, there are two parents
                else:
                    cur_level[index] = min(
                        cur_level[index] + upper_level[index - 1],
                        cur_level[index] + upper_level[index]
                    )
        
        # the last level eventually holds min values of all paths
        return min(triangle[-1])

Log in to reply
 

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