My C++ 0ms AC solution


  • 0
    H

    Using rolling array but not improving stack space consumption (output is prototyped inefficiently to be O(n^2) in space).

    class Solution {
    public:
        vector<vector<int>> generate(int numRows) {
            vector<vector<int>> sol;
            if(numRows == 0)    return sol;
            vector<int> row(numRows, 1);
            for(size_t i = 1; i <= numRows; i++) {
                vector<int> tmp(row.begin(), row.begin() + i);
                for(size_t j = 1; j < i-1; j++) {
                    tmp[j] = row[j] + row[j-1];
                }
                for(size_t j = 1; j < i-1; j++) {
                    row[j] = tmp[j];
                }
                sol.push_back(tmp);
            }
            return sol;
        }
    };

Log in to reply
 

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