118. Pascal’s Triangle
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 55.4%
Problem Breakdown
The problem asks us to generate the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it. The input is an integer numRows, which specifies how many rows of the triangle we need to generate. The output should be a list of lists, where each inner list represents a row in Pascal’s triangle.
Inputs:
- An integer
numRows(1 <= numRows <= 30)
Outputs:
- A list of lists containing integers representing the first
numRowsof Pascal’s triangle.
Implicit Constraints/Edge Cases:
- The smallest input is
numRows = 1, which should return[[1]]. - The largest input is
numRows = 30, which requires generating a relatively large triangle but still manageable within the constraints. - There are no negative numbers or duplicates to consider.
Intuition
A brute-force approach would involve manually calculating each element of Pascal’s triangle by iterating through previous rows and summing adjacent elements. However, this approach is inefficient in terms of both time and space complexity because it involves repeated calculations and storing intermediate results unnecessarily.
The key insight is that each row in Pascal’s triangle can be generated based on the previous row using a simple formula: each element (except the first and last) is the sum of the two elements directly above it from the previous row. This allows us to build the triangle iteratively, which is both time-efficient and space-efficient.
Approach
- Initialize the Result List: Start with an empty list
resultthat will store all rows of Pascal’s triangle. - Iterate Over Rows: Use a loop to generate each row from 0 to
numRows - 1. - Generate Each Row:
- For the first row (row index 0), append
[1]toresult. - For subsequent rows, initialize a new list
current_rowwith the first element as1. - Use another loop to fill in the middle elements of
current_rowby summing adjacent elements from the previous row. - Append
1as the last element ofcurrent_row.
- For the first row (row index 0), append
- Append Current Row: Add
current_rowtoresult. - Return Result: After all rows are generated, return the
result.
Complexity Analysis
- Time Complexity: O(numRows^2). This is because we generate each row in linear time relative to its length, and there are
numRowsrows. - Space Complexity: O(numRows^2). We store all elements of Pascal’s triangle in the
resultlist.
Solution
def generate(numRows):
result = []
for i in range(numRows):
current_row = [1] * (i + 1)
if i > 0:
for j in range(1, i):
current_row[j] = result[i - 1][j - 1] + result[i - 1][j]
result.append(current_row)
return result
Edge Cases Handled
- numRows = 1: The function correctly returns
[[1]]. - numRows = 2: The function correctly returns
[[1], [1, 1]]. - numRows = 30: The function efficiently generates the first 30 rows of Pascal’s triangle without running into performance issues.