Pascal's Triangle

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

Building each row from the one above takes O(n²) time for n rows, because the triangle has about n²/2 entries and each one is a single addition. That is optimal, since you have to write every entry of the output. Apart from the output it uses O(1) extra space.

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

Entry k of row r , counting both from 0, is the binomial coefficient C(r, k) , the number of ways to choose k items out of r . The rule that each entry is the sum of the two above it is the identity C(r, k) = C(r-1, k-1) + C(r-1, k) . That is also why row r adds up to 2^r .

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 and no other rows.

Q: Why is Pascal's triangle a dynamic programming problem?

Each entry depends on two smaller subproblems, the entries above it, and those subproblems overlap heavily: plain recursion recomputes them over and over. Building the rows in order stores every subproblem once and reuses it, which turns exponential work into O(n²) .

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. In the fourth row, 3 = 1 + 2 and 3 = 2 + 1. In the fifth row, 4 = 1 + 3, 6 = 3 + 3 and 4 = 3 + 1.

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

+13 hidden tests on Submit

Follow-up

Can you build only the last row in a single array, updating it in place row after row instead of keeping the rows above? 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

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

Compute every entry recursively

Correct, but does not finish on the largest tests

Intuition

Number the rows and the positions inside a row from 0. The definition of the triangle turns into a function: entry(row, col) is 1 when col is 0 or equal to row, the two edges, and otherwise it is entry(row-1, col-1) + entry(row-1, col). Call it for every position of every row and you have the triangle. It is correct because it is the definition, word for word.

The trouble is how many calls it makes. The recursion only stops at the edges, where it returns 1, so computing an entry with value v takes about 2v calls. Row r adds up to 2^r, so the 30 rows together need about 2^31 calls, more than two billion. The same small entries are recomputed millions of times: entry(2, 1) sits under almost every value below it.

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 recursive version keeps asking for entries of earlier rows, and you are building those rows anyway. So compute the rows in order, top to bottom, and when you fill row r, read the values you need straight from row r-1, which is already done. Each entry then costs one addition. This is dynamic programming in its plainest form: the table of smaller answers is the output itself.

Start row r as r + 1 ones, which sets both edges. Then for each inner position c from 1 to r-1, set it to above[c-1] + above[c]. Rows 0 and 1 have no inner positions, so they stay [1] and [1, 1] without a special case.

The triangle has 1 + 2 + ... + n, about n²/2, entries, and each takes constant time, so the work is O(n²). Apart from the output, which you have to return anyway, the method needs no extra memory. For numRows = 30 that is 465 entries 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

The loops are short, so the mistakes are about bounds and about the first rows.

Returning numRows + 1 rows. If you number rows from 0, the last one you need is row numRows-1.
Running the inner loop over the edges. Position 0 has no left parent and position row has no right parent, so reading above[col-1] or above[col] there goes out of bounds. Fill only positions 1 to row-1.
Writing a range that breaks on the 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. Guard them, or start the inner positions as ones so rows 0 and 1 need no loop.
Computing entries with factorials. C(29, 14) fits in an int, but 29! overflows even a 64-bit integer, so a formula built on factorials prints wrong numbers on the lower rows.
Reusing one array for every row. If you append the same array each time and then change it, every row in the answer ends up as the last one.

Frequently asked questions4

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

Building each row from the one above takes O(n²) time for n rows, because the triangle has about n²/2 entries and each one is a single addition. That is optimal, since you have to write every entry of the output. Apart from the output it uses O(1) extra space.

How is Pascal's triangle related to binomial coefficients?

Entry k of row r, counting both from 0, is the binomial coefficient C(r, k), the number of ways to choose k items out of r. The rule that each entry is the sum of the two above it is the identity C(r, k) = C(r-1, k-1) + C(r-1, k). That is also why row r adds up to 2^r.

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 and no other rows.

Why is Pascal's triangle a dynamic programming problem?

Each entry depends on two smaller subproblems, the entries above it, and those subproblems overlap heavily: plain recursion recomputes them over and over. Building the rows in order stores every subproblem once and reuses it, which turns exponential work into O(n²).

Python

def generate(numRows):
    # Write code here

Test cases

Case 1

Case 2

Input

numRows = 5

Expected

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