Pascal's Triangle
LeetCode #118 · Easy · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Build row by row using previous row values
Strategy
- 1Handle base cases for numRows 1 and 2.
- 2For each subsequent row i (1-indexed from 3):
Time
O(numRows^2)
Space
O(1)
extra space (excluding the result)
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- numRows = 5
- Output:
- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Constraints
- •1 <= numRows <= 30
C++ Solution
solution.cpp
class Solution {
public:
vector<vector<int>> generate(int numRows) {
if (numRows == 1) return {{1}};
if (numRows == 2) return {{1}, {1, 1}};
vector<vector<int>> res = {{1}, {1, 1}};
for (int i = 3; i <= numRows; i++) {
vector<int> row(i);
row[0] = row[i - 1] = 1;
for (int j = 1; j <= i / 2; j++) {
row[j] = row[i - j - 1] = res[i - 2][j - 1] + res[i - 2][j];
}
res.push_back(row);
}
return res;
}
};