{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Pascal's Triangle – Solution & Complexity

Interview solutions
/
Pascal's Triangle

Solution Walkthrough

  1. Step 1: Understand the Pattern

    • Row 0 is [1].
    • Every later row begins and ends with 1.
    • An interior value at position j equals the sum of positions j-1 and j in the previous row.

  2. Step 2: Build Row by Row

    • Start the result with the first row [1].
    • For each new row, walk the previous row and add adjacent pairs.
    • Wrap the sums with a leading and trailing 1.
    def generate(num_rows):
    triangle = []
    for r in range(num_rows):
        row = [1] * (r + 1)
        for j in range(1, r):
            row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j]
        triangle.append(row)
    return triangle

  3. Step 3: Rolling Previous Row

    • You never need more than the previous row to build the next one.
    • Derive the next row by zipping the previous row shifted by one.
    • This keeps the logic to pure additions.
    def generate(num_rows):
    triangle = []
    prev = []
    for _ in range(num_rows):
        row = [1]
        for a, b in zip(prev, prev[1:]):
            row.append(a + b)
        if prev:
            row.append(1)
        triangle.append(row)
        prev = row
    return triangle

  4. Step 4: Final Solution and Complexity

    • Each of the numRows rows costs work proportional to its length.
    • Total time is O(numRows^2).
    • Space is O(numRows^2) for the returned triangle.
    def generate(num_rows: int) -> list:
    triangle = []
    for r in range(num_rows):
        row = [1] * (r + 1)
        for j in range(1, r):
            row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j]
        triangle.append(row)
    return triangle

FAQ

See also

Practice Pascal's Triangle online (run code in the browser)Missing Number solution (easy)Plus One solution (easy)Unique Paths solution (medium)3Sum solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?