Problem
Given an integer numRows, return the first numRows of Pascal’s triangle.
Example
Input: 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]Solution
Each row starts and ends with 1. Middle values are sum of the two values above.
def generate(num_rows):
triangle = []
for i in range(num_rows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = triangle[i-1][j-1] + triangle[i-1][j]
triangle.append(row)
return trianglefunction generate(numRows) {
const triangle = [];
for (let i = 0; i < numRows; i++) {
const row = new Array(i + 1).fill(1);
for (let j = 1; j < i; j++) {
row[j] = triangle[i-1][j-1] + triangle[i-1][j];
}
triangle.push(row);
}
return triangle;
}vector<vector<int>> generate(int numRows) {
vector<vector<int>> triangle;
for (int i = 0; i < numRows; i++) {
vector<int> row(i + 1, 1);
for (int j = 1; j < i; j++) {
row[j] = triangle[i-1][j-1] + triangle[i-1][j];
}
triangle.push_back(row);
}
return triangle;
}public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) row.add(1);
for (int j = 1; j < i; j++) {
row.set(j, triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));
}
triangle.add(row);
}
return triangle;
}Complexity
- Time: O(n²)
- Space: O(n²)
Explanation
Each row depends only on the previous row. We build top-down, using the formula row[j] = above[j-1] + above[j].
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?