118. Pascal's Triangle

Problem¶

Return the first numRows rows of Pascal's triangle, where each row starts and ends with 1, and each inner value is the sum of the two values above it.

Example:
- Input: numRows = 5
- Output: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

Key trick¶

Build each row from the previous one.

Start every row with 1
Add pairwise sums from the previous row
End every row with 1

Trap¶

Common mistakes are small but frequent.

Off-by-one in row count
Forgetting that the first and last element are always 1
Special-casing too much instead of using one uniform loop
Mutating the previous row instead of creating a new one

Why is it interesting?¶

It tests simple iterative construction cleanly.

Good practice for list building
Easy to overcomplicate, so code clarity matters
Introduces the idea of deriving state from the previous state

Python solution¶

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        triangle = []

        for _ in range(numRows):
            if not triangle:
                triangle.append([1])
                continue

            prev = triangle[-1]
            row = [1]

            # Inner values come from adjacent pairs in the previous row.
            for i in range(1, len(prev)):
                row.append(prev[i - 1] + prev[i])

            row.append(1)
            triangle.append(row)

        return triangle

Comment on my solution¶

Your solution is correct and interview-good, but it can be simpler.

The numRows == 1 and numRows == 2 special cases are unnecessary
One loop handles all cases cleanly
zip(prev_row, prev_row[1:]) is a nice Pythonic touch
Overall time is \(O(n^2)\) and optimal for output size

import pytest

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        if numRows == 1:
            return [[1]]
        if numRows == 2:
            return [[1], [1, 1]]
        out = [[1], [1, 1]]
        for row_idx in range(2, numRows):
            prev_row = out[-1]
            row = [1]
            for a,b in zip(prev_row, prev_row[1:]):
                row.append(a + b)
            row.append(1)
            out.append(row)
        return out

@pytest.mark.parametrize(
    ("numRows", "expected"),
    [
        (1, [[1]]),
        (2, [[1], [1, 1]]),
        (5, [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]),
    ]
)
def test_generate(numRows, expected):
    assert Solution().generate(numRows) == expected