Pascal's Triangle II
LeetCode #119 · Easy · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Build rows iteratively
Strategy
- 1Handle base cases for rowIndex 0 and 1.
- 2Build the triangle row by row up to rowIndex.
- 3Use symmetry to fill each row efficiently.
- 4Return the requested row.
Time
O(rowIndex^2)
Space
O(rowIndex^2)
storing all rows
Problem description(from LeetCode)
Given an integer rowIndex, return the rowIndex-th (0-indexed) row of the Pascal's triangle.
Examples
Example 1
- Input:
- rowIndex = 3
- Output:
- [1,3,3,1]
Constraints
- •0 <= rowIndex <= 33
C++ Solution
solution.cpp
class Solution {
public:
vector<int> getRow(int rowIndex) {
if (rowIndex == 0) return {1};
if (rowIndex == 1) return {1, 1};
vector<vector<int>> res = {{1}, {1, 1}};
for (int i = 3; i <= rowIndex + 1; 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[rowIndex];
}
};