EasyArrayDynamic ProgrammingUpdated Sep 2026

118. Pascal's Triangle

Asked at Bloomberg

Difficulty

Easy

Time

O(numRows^2)

Space

O(numRows^2)

Pattern

Array

Companies

1

Problem

You are given an integer numRows. Build and return the first numRows rows of Pascal's triangle as a list of lists.

Row numbering starts at 1. Row 1 is just [1]. Every later row starts with 1 and ends with 1. Each value in between is the sum of the two values directly above it in the previous row: the one above-left and the one above-right.

So row r has exactly r entries, and for an inner position c we have row[c] = prev[c - 1] + prev[c], where prev is the row just above. Return the rows in order, top to bottom.

Each value is the sum of the two above it

triangle01234123451111211331146414 comes from the two blue cells above it: 1 + 3
Row 5 is built from row 4: 1, then 1+3, 3+3, 3+1, then 1.

Constraints

  • ●1 <= numRows <= 30

Examples

Example 1
InputnumRows = 5
Output[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
WhyRow 1 is [1]. Row 2 is [1,1]. In row 3 the middle value is 1+1=2. In row 4 the inner values are 1+2=3 and 2+1=3. In row 5 they are 1+3=4, 3+3=6 and 3+1=4.
Example 2
InputnumRows = 1
Output[[1]]
WhyOnly the first row is requested, and that row is always just the single value 1.

Asked At

1 companies
CompanyDifficulty
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Each row r has r + 1 entries. The first and last are always 1.

2

Key insight: an inner entry row[c] equals prev[c - 1] + prev[c], where prev is the row above. So you only ever need the previous row to build the next.

3

Build rows one at a time: start with [1], then for each new row create an array of ones and fill positions 1..r-1 from the previous row.

4

Follow-up you may get: return only row k using O(k) space by updating a single array from right to left.

Optimal Approach

Step 1: res = [].
Step 2: For r in 0..numRows-1:
row = [1] * (r + 1)
For c in 1..r-1: row[c] = res[r-1][c-1] + res[r-1][c]
Append row to res.
Step 3: Return res.

The total number of values produced is 1 + 2 + ... + numRows.

Time: O(numRows²). Space: O(numRows²) for the output.

Build one row from the row above

prev (row 4)13310123The previous row is all we need to make the next onerow 51464101234Inner cells: 1+3=4, 3+3=6, 3+1=4; the ends stay 1row[c] = prev[c-1] + prev[c]row[0] = row[r-1] = 1
Start each row as all ones, then fill the inner positions from the previous row.
ComplexityTime O(numRows^2)Space O(numRows^2)The triangle holds 1+2+...+numRows values, so both building it and storing it cost about numRows^2.

What Trips People Up in Real Interviews

1

Off-by-one on the inner loop. Only indices 1..r-1 are sums; touching index 0 or r reads outside the previous row.

2

Computing each value with a combination formula C(r, c). It works, but factorials overflow quickly and it misses the point — the interviewer wants the DP relationship.

3

Mutating the previous row in place while still reading from it. Build a fresh row (or iterate right to left if you are asked for the single-row version).

4

Handling numRows = 1 as a special case. The loop already handles it — fewer branches is better.

Solution Code

O(numRows^2) time
def generate(numRows):
    res = []
    for r in range(numRows):
        row = [1] * (r + 1)
        for c in range(1, r):
            row[c] = res[r - 1][c - 1] + res[r - 1][c]
        res.append(row)
    return res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Pascal's Triangle problem?

Pascal's Triangle asks you to generate the first `numRows` rows of Pascal's triangle, where each row starts and ends with 1 and every inner value is the sum of the two values directly above it. It is a gentle introduction to building each DP state from the previous one.

How do you solve Pascal's Triangle?

The optimal approach runs in O(numRows^2) time and O(numRows^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Pascal's Triangle?

Pascal's Triangle is asked at Bloomberg. It is a easy difficulty problem.

What are common mistakes on Pascal's Triangle?
  • Off-by-one on the inner loop. Only indices `1..r-1` are sums; touching index 0 or `r` reads outside the previous row.
  • Computing each value with a combination formula `C(r, c)`. It works, but factorials overflow quickly and it misses the point — the interviewer wants the DP relationship.
  • Mutating the previous row in place while still reading from it. Build a fresh row (or iterate right to left if you are asked for the single-row version).
  • Handling `numRows = 1` as a special case. The loop already handles it — fewer branches is better.