Pascal's Triangle: Row-by-Row Construction

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

This is LeetCode 118: Pascal's Triangle, and it is one of the best problems for learning how to construct results row by row using values from the previous row. The pattern it teaches appears in grid DP problems, combinatorics, and anywhere you build a layer from the layer before it.

Why this problem matters

Pascal's triangle looks like a math curiosity, but the underlying mechanic is practical. You are building a 2D structure where each element depends on its neighbors in the previous row. That is the same dependency pattern behind problems like Unique Paths and Minimum Path Sum.

What makes this problem a good starting point is that there is no optimization step. You are not minimizing or maximizing anything. You are just constructing the triangle exactly as defined. That lets you focus entirely on the row-building mechanic without getting distracted by recurrence choices.

The approach

The key insight is that you do not need to think about the entire triangle at once. You build it one row at a time:

1. Row 0 is always [1].
2. For every subsequent row, the first and last elements are 1.
3. Every middle element at position j equals row[i-1][j-1] + row[i-1][j], the sum of the two elements directly above it.

That is the entire algorithm. Start with [1], and keep appending new rows until you have numRows of them.

Building the triangle step by step

Let's trace through numRows = 5 to see exactly how each row is constructed from the one above it.

Each row starts and ends with 1. The middle values come from adding adjacent pairs in the previous row. By the time you finish row 4, you have the complete triangle: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]].

The solution

def generate(numRows):
    triangle = [[1]]

    for i in range(1, numRows):
        prev = triangle[i - 1]
        row = [1]
        for j in range(1, i):
            row.append(prev[j - 1] + prev[j])
        row.append(1)
        triangle.append(row)

    return triangle

Walkthrough

Here is what happens for numRows = 5:

• i = 1: prev = [1]. No middle elements (the inner loop does not run since range(1, 1) is empty). row = [1, 1].
• i = 2: prev = [1, 1]. Inner loop runs for j = 1: prev[0] + prev[1] = 1 + 1 = 2. row = [1, 2, 1].
• i = 3: prev = [1, 2, 1]. Inner loop runs for j = 1 and j = 2: 1 + 2 = 3, then 2 + 1 = 3. row = [1, 3, 3, 1].
• i = 4: prev = [1, 3, 3, 1]. Inner loop: 1 + 3 = 4, 3 + 3 = 6, 3 + 1 = 4. row = [1, 4, 6, 4, 1].

The result is [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]].

Notice the structure: row i has exactly i + 1 elements. The inner loop runs i - 1 times (for the middle elements), and you bookend with 1 on both sides.

Complexity analysis

Time: O(n^2) where n is numRows. Row i has i + 1 elements, so the total work is 1 + 2 + 3 + ... + n = n(n+1)/2, which is O(n^2).

Space: O(n^2) for the output triangle itself. There is no way to avoid this since the problem asks you to return the full triangle. If you only count auxiliary space beyond the output, it is O(n) for the current row being built.

There is no way to reduce the time complexity here. You need to produce every element in the triangle, and there are O(n^2) of them.

Edge cases

• numRows = 1: return [[1]]. Just the single element. Your loop does not execute at all, and the initial [[1]] is the correct answer.
• numRows = 2: return [[1], [1, 1]]. The inner loop for i = 1 produces no middle elements since range(1, 1) is empty.

Both of these are handled naturally by the solution without any special-case code, which is a sign that the algorithm is well-structured.

The building blocks

This problem is built on two reusable patterns:

Iterative row construction. You build a result layer by layer, where each layer depends only on the previous one. This is the same mechanic behind bottom-up DP: you do not need the entire history, just the last row. The pattern shows up whenever you construct sequences where element i depends on elements from step i - 1.

Neighbor sum pattern. Each interior value is computed as the sum of two adjacent values from the previous row: prev[j-1] + prev[j]. This exact dependency structure appears in grid DP problems where dp[r][c] depends on dp[r-1][c-1] and dp[r-1][c]. Recognizing "each cell depends on its neighbors in the previous layer" is a transferable skill.

These two building blocks combine in many other problems:

• Unique Paths (LeetCode 62): each cell depends on the cell above and to the left, and you can optimize to a single row.
• Minimum Path Sum (LeetCode 64): same row-by-row construction, but with a min operation instead of a sum.
• Pascal's Triangle II (LeetCode 119): return just the k-th row, which you can do in O(k) space by updating a single row in place.

From understanding to recall

You have walked through the construction step by step, and the logic makes sense. But understanding how to build Pascal's triangle and being able to write the solution from scratch under time pressure are different skills. The gap between "I see how it works" and "I can produce it cold" is where most people get stuck.

Spaced repetition closes that gap. You revisit this problem at increasing intervals, each time writing the nested loop structure, getting the inner loop bounds right (range(1, i)), and remembering to bookend with 1. After a few repetitions, the row-construction pattern becomes automatic.

The iterative row construction and neighbor sum patterns are part of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Climbing Stairs - The simplest dynamic programming problem, teaching the same "build from previous values" idea in 1D
• Unique Paths - 2D grid DP where each cell depends on its neighbors, the natural next step after Pascal's Triangle