LeetCode 118: Pascal's Triangle

Problem Restatement

We are given an integer:

numRows

We need to generate the first numRows rows of Pascal’s Triangle.

In Pascal’s Triangle:

• The first and last number of every row are 1.
• Every interior value equals the sum of the two numbers directly above it.

The official problem asks us to return the first numRows rows. (leetcode.com)

For example:

numRows = 5

The output is:

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

Input and Output

The function shape is:

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        ...

Examples

For:

numRows = 1

the triangle is:

[
    [1]
]

For:

numRows = 5

the rows are built step by step.

Row 0:

[1]

Row 1:

[1, 1]

Row 2:

[1, 2, 1]

because:

2 = 1 + 1

Row 3:

[1, 3, 3, 1]

because:

3 = 1 + 2
3 = 2 + 1

First Thought: Build Rows One by One

Each row depends only on the previous row.

So instead of computing combinations directly, we can generate rows incrementally.

For every new row:

• Start with 1.
• Compute interior values using the previous row.
• End with 1.

This naturally forms a dynamic programming process.

Key Insight

Suppose the previous row is:

[1, 3, 3, 1]

The next row starts and ends with 1:

[1, ?, ?, ?, 1]

Each interior value comes from the two values above:

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

So the next row becomes:

[1, 4, 6, 4, 1]

The rule is:

for interior positions.

Algorithm

Initialize:

ans = []

For each row index i:

1. Create a row filled with 1s of length i + 1.
2. For every interior position:
   1. Compute the sum of the two values above.
3. Append the row to the answer.

Return the completed triangle.

Correctness

The algorithm builds the triangle row by row.

Each row begins and ends with 1, which matches the definition of Pascal’s Triangle.

For every interior position j, the algorithm computes:

These are exactly the two numbers directly above the current position in Pascal’s Triangle.

Therefore, every interior value is correct.

Since each row is built from the previous row using the Pascal recurrence rule, every generated row matches Pascal’s Triangle exactly.

Thus, after numRows iterations, the algorithm correctly returns the first numRows rows.

Complexity

The output itself contains:

values.

Implementation

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

        for i in range(numRows):
            row = [1] * (i + 1)

            for j in range(1, i):
                row[j] = ans[i - 1][j - 1] + ans[i - 1][j]

            ans.append(row)

        return ans

Code Explanation

The answer list stores all rows:

ans = []

Each row has length:

i + 1

Create the row initially filled with 1s:

row = [1] * (i + 1)

The first and last values remain 1.

Now compute interior values:

for j in range(1, i):

Use the previous row:

row[j] = ans[i - 1][j - 1] + ans[i - 1][j]

Append the completed row:

ans.append(row)

Finally:

return ans

Testing

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

        for i in range(numRows):
            row = [1] * (i + 1)

            for j in range(1, i):
                row[j] = ans[i - 1][j - 1] + ans[i - 1][j]

            ans.append(row)

        return ans

def run_tests():
    s = Solution()

    assert s.generate(1) == [
        [1]
    ]

    assert s.generate(2) == [
        [1],
        [1, 1],
    ]

    assert s.generate(5) == [
        [1],
        [1, 1],
        [1, 2, 1],
        [1, 3, 3, 1],
        [1, 4, 6, 4, 1],
    ]

    assert s.generate(6) == [
        [1],
        [1, 1],
        [1, 2, 1],
        [1, 3, 3, 1],
        [1, 4, 6, 4, 1],
        [1, 5, 10, 10, 5, 1],
    ]

    print("all tests passed")

run_tests()

Test meaning: