119. Pascal’s Triangle II
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.5%
Problem Breakdown
The problem asks us to return the rowIndex-th row of Pascal’s triangle. Pascal’s triangle is a triangular array of the binomial coefficients. Each number in the triangle is the sum of the two numbers directly above it.
Inputs:
- An integer
rowIndex(0-indexed), which specifies which row of Pascal’s triangle to return.
Outputs:
- A list of integers representing the
rowIndex-th row of Pascal’s triangle.
Implicit Constraints or Tricky Edge Cases:
- The input
rowIndexcan be as large as 33, so the solution should be efficient in terms of both time and space. - The first row (
rowIndex = 0) is[1]. - The second row (
rowIndex = 1) is[1, 1].
Intuition
A brute-force approach would involve generating all rows up to rowIndex using a nested loop. However, this approach has a time complexity of O(rowIndex^2) and uses O(rowIndex^2) space, which is inefficient given the constraints.
The key insight is that each row in Pascal’s triangle can be generated from the previous row by summing adjacent elements. This allows us to build the triangle row by row using only O(rowIndex) extra space.
Approach
- Initialize an array
rowwith all elements set to 1, representing the first row of Pascal’s triangle. - For each subsequent row up to
rowIndex, update the elements in place:- Start from the second last element and move towards the first element.
- Each element at position
jis updated to be the sum of itself and the element directly above it (positionj-1).
- After processing all rows, the array
rowwill contain therowIndex-th row of Pascal’s triangle.
Complexity Analysis
- Time Complexity: O(rowIndex^2) because we need to update each element in the row for each row up to
rowIndex. - Space Complexity: O(rowIndex) because we only store one row at a time.
Solution
def getRow(rowIndex: int) -> List[int]:
# Initialize the first row of Pascal's triangle
row = [1] * (rowIndex + 1)
# Generate each row up to rowIndex
for i in range(1, rowIndex + 1):
# Update the row from right to left
for j in range(i - 1, 0, -1):
row[j] += row[j - 1]
return row
Edge Cases Handled
- rowIndex = 0: The function returns
[1], which is the first row of Pascal’s triangle. - rowIndex = 1: The function returns
[1, 1], which is the second row of Pascal’s triangle. - rowIndex = 33: The function efficiently computes the 33rd row using O(rowIndex) space.