We can generate row by row iteratively. Each row starts and ends with 1. Every interior element at index j in row i is the sum of elements at index j-1 and j from row i-1.
// Pseudocode:
// 1. If numRows == 0, return [].
// 2. Init res = [[1]].
// 3. Loop for i from 1 to numRows - 1:
// 4. Create a new row initialized with 1s of size i+1.
// 5. Loop for j from 1 to length of new row - 1:
// 6. row[j] = res.back()[j-1] + res.back()[j]
// 7. Append row to res.
// 8. Return res.
class Solution {
public:
vector<vector<int>> generate(int numRows) {
if (numRows == 0) return {};
vector<vector<int>> res;
res.push_back({1});
for (int i = 1; i < numRows; i++) {
vector<int> prev_row = res.back();
vector<int> new_row(i + 1, 1);
for (int j = 1; j < i; j++) {
new_row[j] = prev_row[j-1] + prev_row[j];
}
res.push_back(new_row);
}
return res;
}
};Time: O(numRows^2) to generate all numbers. Space: O(numRows^2) to store the result.
- numRows = 1. Returns 1.
A simple DP or simulation problem. The key is correctly mapping the indices from the previous row to the current row. current[j] = prev[j-1] + prev[j].