# Without using any extra space

• // 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

}
``````

};

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