Pascal's Triangle

Q: What is the time complexity of generating Pascal's triangle?

O(n²) for n rows: the triangle has about n²/2 entries and each is one addition. That is optimal, since you must write every entry of the output. The extra space beyond the output is O(1) .

Q: How is Pascal's triangle related to binomial coefficients?

Entry k of row r , counting from 0, is C(r, k) , the number of ways to choose k items out of r . The sum rule is the identity C(r, k) = C(r-1, k-1) + C(r-1, k) , and row r adds up to 2^r , the number of subsets of r items.

Q: Can you compute one row without building the rows above it?

Yes. Start with 1 and get each next entry from the previous one: C(r, k) = C(r, k-1) × (r-k+1) / k . Multiply before you divide so the division is exact, and use a 64-bit integer for the product. Row r then takes O(r) time.

EasyDynamic programming

+10

In Pascal's triangle, the first row is [1]. Every later row is one entry longer, starts and ends with 1, and each entry in between is the sum of the two entries directly above it. You get an integer numRows. Return the first numRows rows of the triangle, top row first, each row as an array of integers.

Function

generate(numRows: integer) → integer-2d-array

numRowsinteger: how many rows of the triangle to build
Returnsinteger-2d-array: the first numRows rows, top row first

Constraints

1 ≤ numRows ≤ 30
Every entry of the first 30 rows fits in a 32-bit signed integer. The largest is 77558760, in the middle of row 30.

Examples

Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation: Each inner entry adds the two above it. Row four: 3 = 1 + 2 and 3 = 2 + 1. Row five: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Input: numRows = 1
Output: [[1]]
Explanation: With one row, the triangle is only its top, [1].

Follow-up

Can you keep only one array and update it in place, row after row? Which way must the inner loop run, and why?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

An entry is the sum of two entries in the row above. Evaluating that rule from scratch for every entry recomputes the same values, and the work doubles with each row. The rows you return are the stored answers to those smaller problems, so build the triangle top down, each row from the one before it.

Compute every entry recursively

Correct, but does not finish on the largest tests

Intuition

Number rows and positions from 0. The definition becomes a function: entry(row, col) is 1 on the edges, where col is 0 or row, and otherwise entry(row-1, col-1) + entry(row-1, col). It is correct because it is the definition.

The recursion stops only at the edges, which return 1, so an entry of value v takes about 2v calls. Row r adds up to 2^r, so 30 rows need about 2^31 calls, more than two billion.

Algorithm

Write entry(row, col): return 1 if col is 0 or col equals row.
Otherwise return entry(row-1, col-1) + entry(row-1, col).
For each row from 0 to numRows-1, collect entry(row, col) for every col from 0 to row.
Return the list of rows.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Build each row from the row above

Intuition

The recursion keeps asking for entries of earlier rows, and you build those rows anyway. So compute the rows top to bottom, and while you fill row r, read row r-1, which is already done. Each entry costs one addition: the table of smaller answers is the output itself.

Starting each row as r + 1 ones sets both edges, so rows 0 and 1, which have no inner positions, need no special case. The triangle has 1 + 2 + ... + n, about n²/2, entries, so the work is O(n²) with no memory beyond the output: 465 entries for 30 rows instead of two billion calls.

Algorithm

Start with an empty list of rows.
For each row from 0 to numRows-1, create row + 1 ones.
For each col from 1 to row-1, set it to the sum of positions col-1 and col of the previous row.
Append the row and continue. Return the list.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Pitfalls and edge cases

Returning numRows + 1 rows. Numbered from 0, the last row you need is numRows-1.
Running the inner loop over the edges. Position 0 has no left parent and position row has no right one, so reading them goes out of bounds.
A range that breaks on small rows. Swift's 1..<row crashes when row is 0, and R's 2:(row-1) counts down to 1 when row is 2.
Computing entries with factorials. C(29, 14) fits in an int, but 29! overflows even a 64-bit integer.
Appending the same array for every row and then changing it. Every row in the answer becomes the last one.

Frequently asked questions3

What is the time complexity of generating Pascal's triangle?

O(n²) for n rows: the triangle has about n²/2 entries and each is one addition. That is optimal, since you must write every entry of the output. The extra space beyond the output is O(1).

How is Pascal's triangle related to binomial coefficients?

Entry k of row r, counting from 0, is C(r, k), the number of ways to choose k items out of r. The sum rule is the identity C(r, k) = C(r-1, k-1) + C(r-1, k), and row r adds up to 2^r, the number of subsets of r items.

Can you compute one row without building the rows above it?

Yes. Start with 1 and get each next entry from the previous one: C(r, k) = C(r, k-1) × (r-k+1) / k. Multiply before you divide so the division is exact, and use a 64-bit integer for the product. Row r then takes O(r) time.

def generate(numRows):
    # Write code here

Test #1

Test #2

Argument

numRows = 5

Expected Output

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