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 as shown:
Example 1:
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1 Output: [[1]]
Constraints:
1 <= numRows <= 30
This problem asks to generate Pascal's Triangle up to a given number of rows (numRows
). Pascal's Triangle is a triangular array where each number is the sum of the two numbers directly above it.
Approach:
The most straightforward approach is to simulate the construction of Pascal's Triangle row by row. We can build this iteratively.
[1]
.1
.Code Explanation (Python):
from itertools import pairwise # For convenient pairwise summation
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return [] #Handle edge case of 0 rows
f = [[1]] # Initialize with the first row
for i in range(1, numRows): # Iterate from the second row
g = [1] # First element is always 1
g.extend([a + b for a, b in pairwise(f[-1])]) #Sum of adjacent elements from the previous row
g.append(1) #Last element is always 1
f.append(g) #Append the new row
return f
The pairwise
function from the itertools
library efficiently provides pairs of consecutive elements from the previous row, simplifying the summation. If you don't want to use itertools
, you can replace this with a simple loop.
Time and Space Complexity:
numRows
rows, and for each row, the number of calculations is proportional to the row number (which is at most numRows
). Therefore, the nested loops give us a quadratic time complexity.f
array, which stores the Pascal's triangle. The total number of elements in the triangle is the sum of integers from 1 to numRows
, which is proportional to n^2
.Code in other languages follow a very similar pattern:
The core logic remains consistent across all languages: initialize the first row, then iteratively build subsequent rows by summing adjacent elements from the previous row. The differences are mainly in the syntax and standard library functions used for array/list manipulation. For example, the Java code uses ArrayList
and List.of
, C++ uses vector
, and so on. The overall structure and time/space complexity analysis are identical.
Example (Python):
If numRows = 5
, the function would produce:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]