118. Pascal’s Triangle

Edited by Charles

Easy · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given an integer numRows, return the first numRows rows of Pascal's Triangle.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem

Given an integer numRows, return the first numRows rows of Pascal's Triangle.

For example:

numRows = 5

we should return:

[
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1]
]

Pascal's Triangle looks like:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1

The key observation is:

Every row of Pascal's Triangle can be generated from the previous row.

We use:

dp[i]

to represent the entire i-th row of Pascal's Triangle.

Since Python uses 0-based indexing:

dp[0] = [1]
dp[1] = [1, 1]
dp[2] = [1, 2, 1]
dp[3] = [1, 3, 3, 1]
...

The first two rows are:

[1]

[1, 1]

Therefore:

dp = [[] for _ in range(numRows)]

dp[0] = [1]
dp[1] = [1, 1]

Since accessing:

dp[1]

requires at least two rows, we separately handle:

if numRows == 1:
    return [[1]]

So the initialization is:

if numRows == 1:
    return [[1]]

dp = [[] for _ in range(numRows)]

dp[0] = [1]
dp[1] = [1, 1]

Every row of Pascal's Triangle has the following structure:

[1] + [middle elements] + [1]

The first and last elements are always:

1

For every middle element:

dp[i][j]

we add the two adjacent elements from the previous row:

dp[i - 1][j - 1] + dp[i - 1][j]

Therefore:

dp[i][j]
=
dp[i - 1][j - 1]
+
dp[i - 1][j]

Consider:

Previous row:

        1     3     3     1
         \   / \   / \   /
          \ /   \ /   \ /
           4     6     4

Current row:

        1     4     6     4     1

For example:

4 = 1 + 3
6 = 3 + 3
4 = 3 + 1

For position j in the current row, its two parents in the previous row are:

j - 1

and:

j

Therefore:

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

We only need to calculate the middle elements.

The first element is already:

1

and the last element is also:

1

Therefore, for the previous row:

dp[i - 1]

we calculate:

for j in range(1, len(dp[i - 1]))

For example:

previous row = [1, 3, 3, 1]

Its length is:

4

Therefore:

range(1, 4)

gives:

j = 1, 2, 3

and we calculate:

j = 1:

dp[i-1][0] + dp[i-1][1]
= 1 + 3
= 4

j = 2:

dp[i-1][1] + dp[i-1][2]
= 3 + 3
= 6

j = 3:

dp[i-1][2] + dp[i-1][3]
= 3 + 1
= 4

So the middle part becomes:

[4, 6, 4]

Then we add 1 to both sides:

[1] + [4, 6, 4] + [1]

giving:

[1, 4, 6, 4, 1]

This allows us to construct one row directly using:

dp[i] = (
    [1]
    + [
        dp[i - 1][j] + dp[i - 1][j - 1]
        for j in range(1, len(dp[i - 1]))
    ]
    + [1]
)

This line directly represents the mathematical structure of Pascal's Triangle:

Current Row

=
[1]

+

[sum of every adjacent pair in the previous row]

+

[1]

Consider:

numRows = 5

Initially:

dp = [
    [1],
    [1, 1],
    [],
    [],
    []
]

Generate Row 3

Previous row:

dp[1] = [1, 1]

Middle elements:

1 + 1 = 2

Therefore:

[1] + [2] + [1]

gives:

dp[2] = [1, 2, 1]

Now:

dp = [
    [1],
    [1, 1],
    [1, 2, 1],
    [],
    []
]

Generate Row 4

Previous row:

dp[2] = [1, 2, 1]

Middle elements:

1 + 2 = 3

2 + 1 = 3

Therefore:

[1] + [3, 3] + [1]

gives:

dp[3] = [1, 3, 3, 1]

Generate Row 5

Previous row:

dp[3] = [1, 3, 3, 1]

Middle elements:

1 + 3 = 4

3 + 3 = 6

3 + 1 = 4

Therefore:

[1] + [4, 6, 4] + [1]

gives:

dp[4] = [1, 4, 6, 4, 1]

Final result:

[
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1]
]

Since we already initialize:

dp[1] = [1, 1]

we could technically start from:

for i in range(2, numRows):

instead of:

for i in range(1, numRows):

because row 1 is already known.

So a slightly cleaner version of the same approach is:

for i in range(2, numRows):

This avoids calculating:

dp[1]

again.

Time Complexity

We generate:

1 + 2 + 3 + ... + numRows

elements.

Therefore:

O(numRows²)

This is already optimal because the output itself contains:

O(numRows²)

numbers.

Space Complexity

The complete Pascal's Triangle contains:

O(numRows²)

elements.

Therefore:

O(numRows²)

space is required for the returned result.

Define:

dp[i] = the i-th row of Pascal's Triangle

Every row has the structure:

[1] + middle + [1]

For each middle position:

dp[i][j]
=
dp[i - 1][j - 1]
+
dp[i - 1][j]

So the entire row can be constructed elegantly as:

dp[i] = (
    [1]
    + [
        dp[i - 1][j] + dp[i - 1][j - 1]
        for j in range(1, len(dp[i - 1]))
    ]
    + [1]
)

The most useful way to remember this problem is:

Pascal's Triangle

current row
=
[1]
+
adjacent pair sums from previous row
+
[1]

Time Complexity:

O(numRows²)

Space Complexity:

O(numRows²)

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 18, 2026

Python solution

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

        dp = [[] for _ in range(numRows)]
        dp[0] = [1]
        dp[1] = [1, 1]

        for i in range(2, numRows):
            dp[i] = (
                [1]
                + [
                    dp[i - 1][j] + dp[i - 1][j - 1]
                    for j in range(1, len(dp[i - 1]))
                ]
                + [1]
            )

        return dp

---

Back to Bonus Dynamic Programming · All Algorithm notes