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

Number: 118

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, Microsoft, Zoho, Mitsogo, Apple, Adobe, Yahoo, tcs, HSBC, Virtusa, X

Problem Description

Generate the first numRows of Pascal's Triangle where each element is the sum of the two numbers directly above it. The first row is [1], and each subsequent row starts and ends with 1.

Key Insights

  • Each row begins and ends with the number 1.
  • Every inner element is the sum of the two elements from the previous row.
  • Only two nested loops are required: one for iterating through the rows and one for computing the inner elements.
  • The algorithm steadily builds the triangle row by row.

Space and Time Complexity

Time Complexity: O(n^2) – We construct each row by iterating through all previous rows. Space Complexity: O(n^2) – We store all the numbers in the triangle.

Solution

This problem is solved by iterative construction of each row. We start with a triangle containing only the first row. For each new row, we set the first and last element to 1. For the inner elements, sum the two adjacent numbers from the previous row. The primary data structure is a list (or array) of lists (or arrays) that holds the triangle. This algorithm uses nested loops: the outer loop to iterate through each row, and the inner loop to compute the inner cells of each row.

Code Solutions

def generate_pascal_triangle(numRows):
    # Initialize the triangle with the first row
    triangle = [[1]]
    
    # Generate each row from the second to numRows
    for row_number in range(1, numRows):
        # Start the new row with the number 1
        row = [1]
        # Get the previous row to compute the current row values
        previous_row = triangle[row_number - 1]
        # Compute the inner elements of the row
        for j in range(1, row_number):
            # Sum of two adjacent numbers from the previous row
            row.append(previous_row[j - 1] + previous_row[j])
        # End the row with the number 1
        row.append(1)
        # Add the constructed row to the triangle
        triangle.append(row)
    
    return triangle

# Example usage:
print(generate_pascal_triangle(5))
← Back to All Questions