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

Difficulty: Easy

Problem Description

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

Key Insights

  • Pascal's Triangle is constructed iteratively.
  • Each row starts and ends with 1.
  • The interior elements of each row are computed as the sum of the two elements directly above it from the previous row.
  • The number of rows is controlled by the numRows input.

Space and Time Complexity

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

Solution

To solve the problem, we can use a list of lists (2D array) to represent Pascal's Triangle. We initialize the triangle with the first row, which is always [1]. For each subsequent row, we create a new list starting with 1, then compute each interior value as the sum of the two values above it from the previous row, and finally end the row with another 1. This process continues until we have constructed the required number of rows.

Code Solutions

def generate(numRows):
    triangle = []
    for row in range(numRows):
        # Start a new row
        current_row = [1] * (row + 1)
        for col in range(1, row):
            # Calculate the value based on the two values above it
            current_row[col] = triangle[row - 1][col - 1] + triangle[row - 1][col]
        triangle.append(current_row)
    return triangle
← Back to All Questions