O(n) solution using list


#1

The solution works just because at nth level we have n leaf nodes

in the solution minimum of the current two leaf nodes is calculated and put back to the list while these two leaf nodes are popped till we reach the single root node

NOTE: take care of the indexes in different loops

> #include <list>

int Solution::minimumTotal(vector<vector<int> > &A) {
    int n = A.size() - 1;
    if(n==0)return A[0][0];
    list<int>l;
    for(int i=0;i<A[n].size();i++)
    l.push_back(A[n][i]);
    while(n--){
        int fir = l.front();
        l.pop_front();
        int sec;
        for(int i = 0;i<A[n].size();i++)
        {
            sec = l.front();
            l.pop_front();
            l.push_back(min(sec,fir)+A[n][i]);
            fir = sec;
        }
    }
    return l.front();
}