Problem statement

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

Example 1

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

Example 2

Input: numRows = 1
Output: [[1]]

Constraints

• 1 <= numRows <= 20

Hints for Pascal's Triangle

1. Hint 1

   Every row starts and ends with 1.

2. Hint 2

   row[j] = prevRow[j-1] + prevRow[j] for the interior entries.

How to solve Pascal's Triangle

Each row is built directly from the one above it: the ends are always 1, and every interior entry is the sum of the two entries diagonally above. Build the rows in order and each one has everything it needs already computed.

Approach

1. Start with the first row, [1].
2. For each subsequent row of length r + 1, set the first and last entries to 1.
3. For each interior index j, set row[j] = prev[j - 1] + prev[j].
4. Append the row and continue until numRows rows exist.

Why it works

This is the additive recurrence for binomial coefficients, C(n, k) = C(n-1, k-1) + C(n-1, k), with the boundary cases C(n, 0) = C(n, n) = 1. Because each row depends only on its immediate predecessor, a single forward pass computes them all with no recomputation — the same values would cost exponentially more to derive independently by a naive recursion.

Complexity

• Time — O(numRows^2)
• Space — O(numRows^2) for the output

Pitfalls

• Row r has r + 1 entries, so the interior loop runs over 1 .. r - 1 only.
• Read the previous row, not the row being built — overwriting in place shifts the sums.
• numRows = 1 must return [[1]], which falls out if the seed row is handled before the loop.
• Entries grow quickly; at 20 rows they still fit comfortably in a 32-bit integer, but the growth is worth noting.

Reference solution

Python

from typing import List

def generate(numRows: int) -> List[List[int]]:
    out = [[1]]
    for i in range(1, numRows):
        prev = out[-1]
        row = [1]
        for j in range(1, i):
            row.append(prev[j - 1] + prev[j])
        row.append(1)
        out.append(row)
    return out[:numRows]

Java

public static int[][] generate(int numRows) {
    int[][] out = new int[numRows][];
    for (int r = 0; r < numRows; r++) {
        out[r] = new int[r + 1];
        for (int j = 0; j <= r; j++) {
            if (j == 0 || j == r) out[r][j] = 1;
            else out[r][j] = out[r - 1][j - 1] + out[r - 1][j];
        }
    }
    return out;
}

C++

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

JavaScript

var generate = function(numRows) {
    const out = [[1]];
    for (let i = 1; i < numRows; i++) {
        const prev = out[i - 1];
        const row = [1];
        for (let j = 1; j < i; j++) row.push(prev[j - 1] + prev[j]);
        row.push(1);
        out.push(row);
    }
    return out.slice(0, numRows);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy