My C++ solution (Only 11ms, O(1) space, O(n) time)


  • 0
    J

    //For each node, save it minimum value from the above adjacent nodes.

    //Watch out first and last node for only save one path.

    //For node in the middle, save current node value in tmp.

    //Compare the sum using tmp

        int m = triangle.size();
        if(m == 1) return triangle[0][0];
        int tmp, n = 0;
        
        for(int i=1; i<m; i++){
            n = triangle[i].size();
            for(int j=0; j<n; j++)
            {
                if(j==0) triangle[i][j]+=triangle[i-1][j];
                else if(j==n-1) triangle[i][j]+=triangle[i-1][j-1];
                else {
                    tmp = (triangle[i-1][j-1]<triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
                    triangle[i][j] += tmp;
                }
            }
        }
        
        //Try to get the min in last row
        tmp = triangle[m-1][0];
        for(int k=0; k<triangle[m-1].size(); k++){
            tmp = std::min(tmp, triangle[m-1][k]);
        }
        return tmp;

Log in to reply
 

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