Pascal's Triangle
Build the first n rows of Pascal's triangle, where each inner value is the sum of the two values above it. A warm-up for building each row of a table from the previous one. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Given an integer numRows, return the first numRows rows of Pascal's triangle as a list of lists.
The triangle is built row by row:
- The first row is
[1]. - Every later row starts and ends with
1. - Every value in between is the sum of the two values directly above it in the previous row: position
jin rowiequalsrow[i-1][j-1] + row[i-1][j].
Row i (counting from 0) has i + 1 values.
Example 1
- Input
- numRows = 4
- Output
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
In the last row, 3 = 1 + 2 and 3 = 2 + 1, taken from the row above.
Example 2
- Input
- numRows = 1
- Output
- [[1]]
Example 3
- Input
- numRows = 6
- Output
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
The middle 10s come from 4 + 6 and 6 + 4.
Constraints
- 1 ≤ numRows ≤ 30
- Every value fits in a 32-bit signed integer for numRows ≤ 30.
- Return the rows in order, top row first.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Pascal's Triangle in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Pascal's Triangle
Pattern: Build each row from the previous row
The definition already tells you the algorithm. Row i depends only on row i - 1, so you build the rows in order and keep them all, since you have to return them anyway.
For each new row, the two edges are always 1. The inside positions are pairwise sums of neighbors in the previous row: walk j from 1 to i - 1 and add prev[j - 1] + prev[j]. The only care needed is around the first two rows, where there are no inside positions at all.
Approach 1: Binomial coefficients from scratch
Each value is C(i, j). Computing every coefficient with factorials works for small inputs but repeats a lot of multiplication and overflows quickly in languages with fixed-width integers, long before the values themselves get large.
Time O(n³) with naive factorials · Space O(n²) for the output
Approach 2: Row by row with pairwise sums
Start with [[1]]. For each row index i from 1 to numRows - 1:
- Let
prevbe the last row. - Build
row = [1], then appendprev[j - 1] + prev[j]forjin1..i-1, then append1. - Add
rowto the result.
Every value is computed once with one addition.
Time O(n²) · Space O(n²) for the output
| Approach | Time | Space |
|---|---|---|
| Binomial coefficients from scratch | O(n³) with naive factorials | O(n²) for the output |
| Row by row with pairwise sums | O(n²) | O(n²) for the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Pascal's Triangle solution in Python
def generate(num_rows: int) -> list[list[int]]:
rows = [[1]]
for i in range(1, num_rows):
prev = rows[-1]
row = [1]
for j in range(1, i):
row.append(prev[j - 1] + prev[j])
row.append(1)
rows.append(row)
return rowsPascal's Triangle solution in JavaScript
function generate(numRows) {
const rows = [[1]];
for (let i = 1; i < numRows; i++) {
const prev = rows[i - 1];
const row = [1];
for (let j = 1; j < i; j++) row.push(prev[j - 1] + prev[j]);
row.push(1);
rows.push(row);
}
return rows;
}Common mistakes
- Appending a trailing 1 to the very first row, which produces `[1, 1]` instead of `[1]`.
- Returning `numRows + 1` rows because the loop bound is off by one.
- Reusing and mutating the same list object for every row, so all rows end up identical.
- Computing values with factorials, which overflows 32-bit or 64-bit integers well before row 30.
What interviewers look for
This is usually a warm-up, so the interviewer is checking that you write clean loops and handle the small cases without special-casing everything. Say the recurrence in one sentence, then code it.
Walk through numRows = 1 and numRows = 2 out loud before you say you're done. Those are where off-by-one errors in the inner loop show up.
Follow-up questions
How would you return only row k using O(k) extra space?
Keep a single array and update it in place from right to left: `row[j] += row[j - 1]` for j from i down to 1, then append 1. Going right to left means you read old values before overwriting them.
Can you compute row k directly without the earlier rows?
Yes. Use `C(k, j) = C(k, j - 1) * (k - j + 1) / j`, starting from 1. Each value comes from the previous one with one multiply and one exact division, giving O(k) time.
Where else does this pattern appear?
Any dynamic programming table where a cell depends only on the row above, like counting grid paths or the knapsack table. The space trick from row k carries over directly.
Companies that ask Pascal's Triangle
Pascal's Triangle is tagged by 96 companies in our interview dataset. The score shows how often it comes up at each company.
- Tata Consultancy Services100%
- Nebius100%
- Te Connectivity100%
- Postman96%
- Twitter93.7%
- Culture Amp90%
- Medallia90%
- Credit Karma87%
- Mozilla86%
- Fireeye85%
- Nylas85%
- Upwork81%
- Sailpoint80%
- Epic Games79%
- Ai Foundation77%
- Veracyte76%
- Clever75%
- Pegasystems74%
- Jabil73%
- Zipline71%
- Clear Street71%
- Nexhealth71%
- Workspan70%
- Mvf68%
and 72 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required