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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Pascal's Triangle II

Difficulty: Easy

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.

Key Insights

  • Each number in Pascal's triangle can be calculated using the values from the previous row.
  • The first and last elements of each row are always 1.
  • The value of an element at position j in row i can be computed as triangle[i-1][j-1] + triangle[i-1][j].
  • We can optimize the space complexity by using a single list to store the current row rather than the entire triangle.

Space and Time Complexity

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

Solution

To solve the problem, we use a list to store the current row of Pascal's triangle. We start with the first row initialized to [1]. For each subsequent row, we calculate the values based on the previous row, using the relationship between the elements. We can optimize the space usage by updating the list in place.

Code Solutions

def getRow(rowIndex):
    row = [1]  # Initialize the first row
    for i in range(rowIndex):
        # Create a new row based on the previous one
        new_row = [1]  # First element is always 1
        for j in range(1, i + 1):
            # Calculate the next element based on the previous row
            new_row.append(row[j - 1] + row[j])
        new_row.append(1)  # Last element is always 1
        row = new_row  # Move to the next row
    return row
← Back to All Questions