{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Pascal's Triangle – Solution & Complexity

Interview solutions
/
Pascal's Triangle

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. 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. 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. 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)Plus One solution (easy)Unique Paths solution (medium)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?