Without using any extra space


  • 0
    M

    // Author : Murat Gevrekci
    // Date : 2016-09-15

    /**********************************************************************************

    • This problem can be used without any extra space !
    • First observation is that a pyramid can be visualized aligned to left without loss of information
    • [a],
    • [b,c],
    • [d,e,f],
    • Second observation is that result can be propagated from bottom of the pyramid to the top layer.
    • Number of elements to operate narrows down by one at each layer. At each element we decide to select which element from the bottom layer.
    • Bottom layer is not processed but used as the initial elements.
    •  [a],            [a],                                [a+min(b+min(d,e),c+min(e+f))                 ]   
      
    •  [b,c], -->  	   [b+min(d,e),  c+min(e+f) ],   -->   [b+min(d,e),                  c+min(e+f)      ], 
      
    •  [d,e,f],		   [d,           e ,   f    ],	       [d,                           e,             f],
      
    • result is ---> "a+min(b+min(d,e),c+min(e+f))"

    **********************************************************************************/

    #include <iostream>
    #include <vector>
    using namespace std;

    class Solution {

    public:
    int minimumTotal(vector<vector<int>>& triangle) {

        int height = triangle.size();
        
    	//Return the top of the pyramid if tree is single layer
        if (height==1)
        {
            return triangle[0][0];
        }
        
        //Propagate the sum from bottom to to top, result will be stored at the top of the pyramid
        for(int heightIndex=height-2;heightIndex>=0;heightIndex--)
        {
            int length = triangle[heightIndex].size();            
            
      //Decide to pick which element for the elements in between
            for(int Index=0;Index<length;Index++)
            {
                triangle[heightIndex][Index] += min(triangle[heightIndex+1][Index],triangle[heightIndex+1][Index+1]);
            }
        }
        
        return triangle[0][0]; // return the top of the pyramid
        
    }
    

    };


Log in to reply
 

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