Pascal's Triangle
Asked at Bloomberg
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
Each row r has r + 1 entries. The first and last are always 1.
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.
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.
Visual walkthrough for numRows = 5:
[1]
[1,1]
[1, 1+1, 1] = [1,2,1]
[1, 1+2, 2+1, 1] = [1,3,3,1]
[1, 1+3, 3+3, 3+1, 1] = [1,4,6,4,1]
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.