# C, Bottom up, No Extra Space, Heap Analogy

• Once we visualize the triangle as a heap, the bottom up approach is easy to understand . We need to essentially allow the smaller values to rise to the top. Let's implement this in-place by utilizing the same triangle array.

Both iterative and recursive solutions are given below:

``````int minimumTotal(int** tr, int tRow, int *tColSizes)
{
int j, i;
for (i = tRow - 2; i >= 0; --i) // upper row selector
for (j = 0; j < tColSizes[i]; ++j) // pick smaller sums
(tr[i])[j] += (tr[i + 1])[j] > (tr[i + 1])[j + 1] ?
(tr[i + 1])[j + 1] : (tr[i + 1])[j];
return (tr[0])[0];
}
``````

Same algorithm, but recursive.

``````int minimumTotal(int** tr, int tRow, int *tColSizes)
{
int j, row = tRow - 2;
for (j = 0; row >= 0 && j < tColSizes[row]; ++j)
(tr[row])[j] += (tr[row + 1])[j] > (tr[row + 1])[j + 1] ?
(tr[row + 1])[j + 1] : (tr[row + 1])[j];
/* Stop recursion when rows < 2 */
return (tRow <= 2) ? **tr : minimumTotal(tr, tRow - 1, tColSizes);
}
``````

• Bottom up is a great idea

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