Pascal's Triangle — Solution

Problem

Given a positive integer numRows, return the first numRows rows of Pascal's triangle — a number triangle where every edge cell is 1 and every interior cell is the sum of the two cells directly above it.

• Input: numRows = 5
• Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
• Explanation: each new row is built by placing 1s at both ends and summing adjacent pairs from the row above.

Counter-example: [1, 3, 3] is not a valid row because it is missing the trailing 1.

Intuition

Every row can be derived entirely from the previous row: the first and last elements are always 1, and each interior element at position j equals prev[j-1] + prev[j]. This means we never need to look back more than one row, and we can build the entire triangle top-down in a single pass.

Solution — Iterative Row Construction

Start with [[1]] and repeatedly derive the next row from the last one — prepend and append 1, then fill the interior by summing adjacent pairs from the previous row.

1. Initialize triangle with the first row [1].
2. Loop from row index 1 up to numRows - 1.
3. For each new row, start with [1].
4. For each interior position j from 1 to len(prev_row) - 1 (inclusive), append prev_row[j-1] + prev_row[j].
5. Append the trailing 1 and add the completed row to triangle.

1def generate(numRows: int) -> list[list[int]]:
2    triangle = [[1]]
3    for i in range(1, numRows):
4        prev_row = triangle[i - 1]
5        current_row = [1]
6        for j in range(1, len(prev_row)):  # interior elements only
7            current_row.append(prev_row[j - 1] + prev_row[j])
8        current_row.append(1)  # every row ends with 1
9        triangle.append(current_row)
10    return triangle

Time: O(numRows²) — we produce approximately numRows²/2 total elements across all rows.

Space: O(numRows²) — the output itself requires storing every element; no extra space beyond the result.

Complexity Summary

Common Mistakes

• Using range(1, len(prev_row) - 1) for the inner loop — this silently skips the last interior element. For prev_row = [1, 2, 1], it computes j=1 only and produces [1, 3, 1] instead of [1, 3, 3, 1]. The correct bound is range(1, len(prev_row)).
• Accessing prev_row[j] + prev_row[j+1] instead of prev_row[j-1] + prev_row[j] — when j reaches len(prev_row) - 1, prev_row[j+1] is an out-of-bounds access. Shifting the index to j-1 and j lets the same range(1, len(prev_row)) bounds work safely.
• Forgetting the trailing 1 — both the leading and trailing 1 must be added explicitly; the inner loop only fills interior positions.
• Starting with an empty triangle list — if triangle starts empty, the loop has no previous row to reference for i=0. Seeding with [[1]] and starting the loop at i=1 avoids this.
• Confusing numRows with row index — if numRows = 5, the output should contain rows at indices 0, 1, 2, 3, 4; the loop range range(1, numRows) produces 4 iterations starting from the already-seeded row 0, which is correct.

Related Problems

• pascals-triangle-ii — return only the kth row in O(k) space instead of the full triangle
• triangle — find the minimum-cost path from top to bottom of a triangular grid using the same row-by-row DP structure
• unique-paths — the number of grid paths equals a value from Pascal's triangle (C(m+n-2, m-1)), connecting combinatorics to DP
• climbing-stairs — another bottom-up DP where each value is derived from the previous one or two values
• coin-change — builds a 1D DP table bottom-up in a similar left-to-right construction pattern