We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pascal's Triangle II

Number: 119

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Adobe, Goldman Sachs, Bloomberg, Yahoo

Problem Description

Given an integer rowIndex, return the rowIndexth (0-indexed) row of Pascal's Triangle. Each element in Pascal's Triangle is the sum of the two numbers directly above it, with boundaries always being 1.

Key Insights

  • Pascal's Triangle is built row-by-row, where each interior element is the sum of the two elements from the previous row.
  • You can generate the row in-place by updating an array from right to left.
  • Iterating in reverse prevents overwriting values that are still needed.
  • The solution can be optimized to use O(rowIndex) extra space.

Space and Time Complexity

Time Complexity: O(rowIndex^2)
Space Complexity: O(rowIndex)

Solution

We use dynamic programming with an in-place update to generate the Pascal's Triangle row. Start with an initial row [1]. For each subsequent row, iterate from right to left (to prevent overwriting necessary values) and update each element as the sum of itself and its left neighbor. Finally, append 1 at the end of each iteration. This approach ensures that we use only O(rowIndex) extra space, while the time complexity remains O(rowIndex^2) overall.

Code Solutions

# Function to generate the specified row of Pascal's Triangle
def getRow(rowIndex):
    # Initialize the result with the first element
    row = [1]
    # Build each row from 1 to rowIndex
    for i in range(1, rowIndex + 1):
        # Update row from rightmost element to leftmost
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]  # Update each element as the sum of the two elements above it
        # Append 1 at the end of the current row
        row.append(1)
    return row

# Example Usage
print(getRow(3))  # Output: [1, 3, 3, 1]
← Back to All Questions