# Pascal's Triangle Problem & Solution

Given an integer `numRows`, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

## C++ Solution

First, you have to initialize the edge cases of rows equals 1 or 2. Second, you need to iterate from 3 all the way up to `numRows` and add up only the inner cells to construct each new row. Note that each new row is initialized with all 1s to avoid complicating the code. And then, only the inner cells are overwritten with the new values which depend on the previous row, specifically each new `row[j]` is the sum of `row[i - 1][j - 1]` and `row[i - 1][j]`. Note that in code we use `row[i - 2]` because the `i` index and `numRows` are off by one.

The runtime complexity of the algorithm is \$O(n^2)\$.

``````#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
vector<vector<int>> generate(int numRows) {
if (numRows == 1) {
return {{1}};
}

if (numRows == 2) {
return {{1}, {1, 1}};
}

vector<vector<int>> result{{1}, {1, 1}};

for (int i = 3; i <= numRows; ++i) {
vector<int> row(i, 1);
for (int j = 1; j < i - 1; ++j) {
row[j] = result[i - 2][j - 1] + result[i - 2][j];
}

result.push_back(row);
}

return result;
}
};
``````

## Start Here

Many paths, there are. Follow yours, you must.