Pascal's Triangle — Row-by-Row Construction

The Problem

Generate the first numRows rows of Pascal’s Triangle. Each entry is the sum of the two entries directly above it, with implicit zeros off the edges. Row 0 is [1], row 1 is [1, 1], row 2 is [1, 2, 1], and so on. The values are the binomial coefficients C(n, k).

The problem is approachable, but it’s a good test of clean index arithmetic and off-by-one discipline.

Intuition

The recurrence is T[i][j] = T[i-1][j-1] + T[i-1][j] with T[i][0] = T[i][i] = 1. So build row by row. For row i, initialize every slot to 1 (this handles both endpoints) and then overwrite interior slots j in [1, i-1] by summing the two cells above in row i - 1. The all-ones initialization is the trick that lets you skip endpoint special cases.

Explanation with Example

For numRows = 5, the triangle builds up like this:

• Row 0: [1]
• Row 1: [1, 1]
• Row 2: start [1, 1, 1], interior j=1: T[1][0] + T[1][1] = 1 + 1 = 2, so [1, 2, 1].
• Row 3: start [1, 1, 1, 1], j=1: 1+2=3, j=2: 2+1=3, so [1, 3, 3, 1].
• Row 4: start [1, 1, 1, 1, 1], j=1: 1+3=4, j=2: 3+3=6, j=3: 3+1=4, so [1, 4, 6, 4, 1].

Verify by binomial coefficients: C(4, 2) = 6, C(4, 1) = 4.

row 0:           1
row 1:          1 1
row 2:         1 2 1
row 3:        1 3 3 1
row 4:       1 4 6 4 1

cell (4,2) = row[3][1] + row[3][2] = 3 + 3 = 6

Code

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

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int k = 0; k <= i; k++) row.add(1);
        for (int j = 1; j < i; j++) {
            row.set(j, triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
        }
        triangle.add(row);
    }
    return triangle;
}

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> triangle;
    for (int i = 0; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        for (int j = 1; j < i; j++) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
        triangle.push_back(row);
    }
    return triangle;
}

Edge Cases

numRows = 0 returns an empty list. numRows = 1 returns [[1]]. numRows = 2 returns [[1], [1, 1]]. The inner loop for j in range(1, i) is empty when i is 0 or 1, so those small cases are handled without special code.

Very large values of numRows would cause big integers in other languages but are fine in Python. The problem caps numRows at 30, so the largest entry is C(29, 14), which is about 67 million — well within 32-bit int range.

Complexity Analysis

Time is O(n^2) where n is numRows. Row i has i + 1 cells, so the total cell count is 1 + 2 + … + n = n(n+1)/2. Each cell is computed in O(1) by adding two values from the previous row.

Space is also O(n^2) because we return the entire triangle. If we only needed one row, we could keep two rolling rows of size O(n) each.

How to Explain It in an Interview

Start by stating the recurrence: T[i][j] = T[i-1][j-1] + T[i-1][j] with T[i][0] = T[i][i] = 1. Mention that this is equivalent to the binomial coefficient C(i, j), which is why Pascal’s Triangle has its number-theoretic significance.

Then describe the implementation: initialize each row with all 1s, fill in the interior by summing two cells from the previous row, append. Walk through rows 0 through 3 on the board. Finish with the O(n^2) bound.

If asked for the kth row only, describe rolling a single row: update each row in place from right to left to avoid clobbering values you still need.

Related Problems

• Pascal’s Triangle II — return just one row, O(k) space.
• Triangle — minimum path sum on a triangle.
• Unique Paths — also expressible as a binomial coefficient.
• All Possible Full Binary Trees — DP on a similar shape.