# Pascal's triangle solution

• Each line in pascal's triangle can be computed from previous line: first and last elements are always '1' and other elements (let it index be i) are sum of two elements of previous line with inices i and i - 1.

``````     1
1   1
\+/
1   2   1
\+/ \+/
1  3   3   1
``````

There is simple c++ implementation:

``````vector<vector<int>> generate(int numRows) {
vector<vector<int>> res(numRows);
for (int i = 0; i < numRows; ++i) {
res[i].push_back(1);
for (int j = 1; j <= i; ++j) {
int el = (j == i) ? 1 : res[i-1][j-1] + res[i-1][j];
res[i].push_back(el);
}
}
return res;
}
};
``````

For each line we compute k-2 elements, where k - current line number, from 2 elements of previous line in constant time plus get constants for first and last elements. Time complexity is O(n^2). Total number of elements is the sum of arithmetic progression, so for N rows number of elements is

``````1+2+..+N = N(N-1)/2
``````

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