Pascals Triangle

Problem

https://leetcode.com/problems/pascals-triangle/

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

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 <= 30

Pattern

Array, Dynamic Programming

Approaches

Iterative

Explanation

Right align the normal presentation of Pascal’s Triangle.

    1        1
   1 1       1 1
  1 2 1  --> 1 2 1
 1 3 3 1     1 3 3 1
1 4 6 4 1    1 4 6 4 1

Observe that a middle entry is the sum of the entry directly above and to the north-west. The first/last entry is always 1.

Code

def generate(n_rows: int) -> list[list[int]]:
    """Generate Pascal's Triangle with ``n_rows``."""
    rows = [[1]]
    for i in range(1, n_rows):
        row = []
        for j in range(i + 1):
            if j == 0 or j == i:
                row.append(1)
            else:
                row.append(rows[i - 1][j - 1] + rows[i - 1][j])
        rows.append(row)
    return rows

Test

>>> from pascals_triangle__iterative import generate
>>> generate(3)
[[1], [1, 1], [1, 2, 1]]
>>> generate(6)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

Complexity

\(n\) is the number of rows in the triangle

Measure	Complexity	Notes
Time	\(O(n^2)\)	triangle is half of a square of side \(n\)
Auxiliary Space	\(O(1)\)

pascals_triangle__iterative.generate(n_rows: int) → list[list[int]]

Generate Pascal’s Triangle with n_rows.