Pascal's Triangle II

Problem Description

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.

Naive Solution

A naive solution would be to construct the entire Pascal's triangle up to the rowIndex and then return the last row. This involves generating each row from 0 to rowIndex, where each element in a row is the sum of the two elements above it in the previous row.

Code (Python)

def getRow_naive(rowIndex):
    triangle = []
    for i in range(rowIndex + 1):
        row = [1] * (i + 1)
        if i > 1:
            for j in range(1, i):
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    return triangle[rowIndex]

Time Complexity

The time complexity is O(rowIndex^2) because we need to compute each element in the triangle up to the rowIndex.

Space Complexity

The space complexity is also O(rowIndex^2) because we store the entire Pascal's triangle.

Optimal Solution

To optimize space, we can use only O(rowIndex) extra space. We can achieve this by updating the row in place. Specifically, we start with a row of all 1s (of length rowIndex + 1) and update the elements from the second element to the second to last element in reverse order. This ensures that we use the values from the previous iteration correctly.

Code (Python)

def getRow_optimal(rowIndex):
    row = [1] * (rowIndex + 1)
    for i in range(1, rowIndex + 1):
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]
    return row

Time Complexity

The time complexity remains O(rowIndex^2) because we still need to iterate through the rows and update the elements.

Space Complexity

The space complexity is reduced to O(rowIndex) because we only store one row of the Pascal's triangle.

Edge Cases

• If rowIndex is 0, return [1]. This is handled correctly in both solutions.
• The problem statement specifies 0 <= rowIndex <= 33. This constraint helps to prevent integer overflow issues when calculating Pascal's triangle elements.