Given an integer rowIndex
, return the rowIndexth
(0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex)
extra space?
This problem asks to generate the rowIndex
-th row of Pascal's Triangle. Pascal's Triangle is a triangular array where each number is the sum of the two numbers directly above it. The solution presented uses a dynamic programming approach for efficiency.
The core idea is to iteratively build each row based on the previous row. We don't need to store the entire Pascal's triangle; we only need to maintain the current row. This significantly reduces space complexity.
Algorithm:
Initialization: Create an array f
of size rowIndex + 1
and initialize all elements to 1. This represents the first row (rowIndex = 0) which contains only 1.
Iteration: Iterate from the second row (i = 2) up to the rowIndex
. For each row i
, update the array f
from right to left. The value at index j
becomes the sum of the values at indices j
and j-1
from the previous row. This efficiently calculates each element in the current row using the previous row's values.
Return: After the iterations are complete, the array f
contains the elements of the rowIndex
-th row of Pascal's Triangle. Return the array.
Time Complexity: The outer loop iterates rowIndex
times. The inner loop iterates at most rowIndex
times in the worst case (last row). Therefore, the overall time complexity is O(rowIndex²). However, it's closer to O(rowIndex * (rowIndex /2)) because the inner loop's iterations reduce on each outer iteration. For the purpose of analysis we can simplify to O(rowIndex²)
Space Complexity: The algorithm uses an array f
of size rowIndex + 1
to store the current row. Thus, the space complexity is O(rowIndex). This is an optimization compared to storing the entire triangle which would require O(rowIndex²) space.
The provided code in various languages implements this optimized dynamic programming approach. Here's a slightly modified version in Python for better readability:
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if rowIndex == 0:
return [1]
row = [1] # Initialize the first row
for i in range(1, rowIndex + 1):
new_row = [1] # Each row starts with 1
for j in range(1, i):
new_row.append(row[j - 1] + row[j]) # Calculate intermediate elements
new_row.append(1) # Each row ends with 1
row = new_row # Update the row for the next iteration
return row
This version explicitly shows the building up of each row and improves readability compared to the in-place update used in the original solution. The time and space complexity remain the same. All other provided languages implement essentially the same algorithm with minor syntax differences.