Pascal's Triangle
Pascal's Triangle is a easy dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (build each row from the previous one), runs in O(n²) time and O(1) extra space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binomial coefficient for every cell) up.
Problem
Given an integer numRows, build the first numRows rows of Pascal’s triangle and return them as a list of rows.
Row 0 is [1]. Each following row is one entry longer: it starts and ends with 1, and every entry in between is the sum of the two entries that sit directly above it (to the upper-left and upper-right) in the previous row.
Examples
Example 1
- Input
numRows = 4- Output
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]- Why
- Each inner value is the sum of the two values just above it, e.g. 3 = 1 + 2.
Example 2
- Input
numRows = 2- Output
[[1], [1, 1]]- Why
- The first two rows have no inner values; every entry is an edge 1.
Constraints
1 <= numRows <= 30
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (binomial coefficient for every cell) | O(n³) | O(1) extra |
| Optimal (build each row from the previous one) | O(n²) | O(1) extra |
1Brute force (binomial coefficient for every cell)
O(n³)There are about n²/2 cells and each one costs up to O(n) multiplications.O(1) extraApart from the output, only a few counters are used.Entry j of row r is the binomial coefficient C(r, j). Compute each one independently with a small multiplicative loop.
- For each row r from 0 to numRows - 1 and each j from 0 to r:
- Compute C(r, j) by multiplying c = c * (r - k) / (k + 1) for k from 0 to j - 1, using a long.
- Append the value to the row; append the row to the answer.
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for (int r = 0; r < numRows; r++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= r; j++) {
long c = 1;
for (int k = 0; k < j; k++) {
c = c * (r - k) / (k + 1);
}
row.add((int) c);
}
res.add(row);
}
return res;
}
}class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for r in range(numRows):
row = []
for j in range(r + 1):
c = 1
for k in range(j):
c = c * (r - k) // (k + 1)
row.append(c)
res.append(row)
return resclass Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
for (int r = 0; r < numRows; r++) {
vector<int> row;
for (int j = 0; j <= r; j++) {
long long c = 1;
for (int k = 0; k < j; k++) {
c = c * (r - k) / (k + 1);
}
row.push_back((int)c);
}
res.push_back(row);
}
return res;
}
};function generate(numRows) {
const res = [];
for (let r = 0; r < numRows; r++) {
const row = [];
for (let j = 0; j <= r; j++) {
let c = 1;
for (let k = 0; k < j; k++) {
c = (c * (r - k)) / (k + 1);
}
row.push(c);
}
res.push(row);
}
return res;
}2Optimal (build each row from the previous one)
O(n²)Each of the roughly n²/2 cells is computed once with a single addition.O(1) extraOnly the output itself is stored.Start with [1]. Every new row begins and ends with 1, and its inner entry j is prev[j - 1] + prev[j]. Each cell is filled in O(1).
- res = [[1]].
- For r from 1 to numRows - 1: let prev = res[r - 1].
- row = [1]; for j from 1 to r - 1 append prev[j - 1] + prev[j]; append 1.
- Add row to res and return res at the end.
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
res.add(List.of(1));
for (int r = 1; r < numRows; r++) {
List<Integer> prev = res.get(r - 1);
List<Integer> row = new ArrayList<>();
row.add(1);
for (int j = 1; j < r; j++) {
row.add(prev.get(j - 1) + prev.get(j));
}
row.add(1);
res.add(row);
}
return res;
}
}class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[1]]
for r in range(1, numRows):
prev = res[-1]
row = [1]
for j in range(1, r):
row.append(prev[j - 1] + prev[j])
row.append(1)
res.append(row)
return resclass Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res = {{1}};
for (int r = 1; r < numRows; r++) {
const vector<int>& prev = res[r - 1];
vector<int> row = {1};
for (int j = 1; j < r; j++) {
row.push_back(prev[j - 1] + prev[j]);
}
row.push_back(1);
res.push_back(row);
}
return res;
}
};function generate(numRows) {
const res = [[1]];
for (let r = 1; r < numRows; r++) {
const prev = res[r - 1];
const row = [1];
for (let j = 1; j < r; j++) {
row.push(prev[j - 1] + prev[j]);
}
row.push(1);
res.push(row);
}
return res;
}Edge cases to test
- numRows = 1: only the single row [1]
- numRows = 30: the largest entries are still below 2^31, so int is enough
Hints
Hint 1
Row r has r + 1 entries, and its first and last entries are always 1.
Hint 2
Every other entry is the sum of the two entries diagonally above it in the previous row.
FAQ
What is the best time complexity for Pascal's Triangle?
Optimal (build each row from the previous one) runs in O(n²) time and O(1) extra extra space. Each of the roughly n²/2 cells is computed once with a single addition.
Which pattern does Pascal's Triangle use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Pascal's Triangle?
Yes. Brute force (binomial coefficient for every cell) takes O(n³) time and O(1) extra space. Entry j of row r is the binomial coefficient C(r, j).
Which edge cases should I test for Pascal's Triangle?
numRows = 1: only the single row [1]; numRows = 30: the largest entries are still below 2^31, so int is enough.