Pascal's Triangle
💻 Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here. 🎮 Play Kodee's Row Rush: a mini-game built on this problem. Works on your phone too. Pass Submit to unlock every round.On this page
Revision notes
Pascal’s Triangle (interview style)
Video: “Pascal’s Triangle” on LearnWithKiriti (Kodee and Mr. Tock). Arrays series, episode 13. LeetCode 118, Easy. Taught as the three ways interviewers ask it: one number, one row, the whole triangle.
Every row starts and ends with 1, and every number inside is the sum of the two numbers above it.
row 1: 1
row 2: 1 1
row 3: 1 2 1
row 4: 1 3 3 1
row 5: 1 4 6 4 1
LeetCode 118: numRows = 5 -> [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]].
| Folder | Question | Approach | Time | Extra space |
|---|---|---|---|---|
Element-Brute/ |
The number at (row, col) | n C r with factorials. Right on paper, but long breaks at 21!: row 22, column 2 prints -1 in Java |
O(row) | O(1) |
Element-Optimal/ |
The number at (row, col) | ans = ans * (row - step) / step, multiply first, then divide |
O(col) | O(1) |
Row-Optimal/ |
One whole row (LeetCode 119 style) | Walk along the row: ans = ans * (row - col) / col |
O(row) | O(1) (the answer list is not counted) |
Triangle-Optimal/ |
The whole triangle (LeetCode 118) | Add the two above, 1 at both ends | O(n^2) | O(1) (the answer is not counted) |
Triangle-RowFormula/ |
The whole triangle (LeetCode 118) | Call the row formula for every row | O(n^2) | O(1) (the answer is not counted) |
Rows and columns count from 1, the way interviewers usually say them, so the number at (row, col) is C(row-1, col-1). Example: (5, 3) = C(4, 2) = 6.
Rebuild it
Add the two above. Multiply, then divide. Never a factorial.
- Every number counts the paths from the top down to it: one path to an edge, and the paths to an inside cell are the paths to its two parents added up. That count is n C r.
- Next number from the previous one:
ans = ans * (row - col) / col. The division is always exact, because after every stepansis itself a binomial (a whole number of paths). Divide first and it breaks: (6, 3) gives 8 instead of 10. - Overflow: with a 32-bit
intand multiply-then-divide, row index 30 (the 31st row) is the first to overflow (145,422,675 x 16 = 2,326,762,800). LeetCode 118 stops at 30 rows (biggest number C(29,14) = 77,558,760), sointfits. For bigger rows, uselong. - The whole triangle is O(n^2), and nothing can beat that: the answer itself has n(n+1)/2 numbers.
Practise it next to the video: the free Kodee Practice Chrome extension (link in the video description).
Related: Pascal’s Triangle II (LeetCode 119) is exactly Row-Optimal/.
See the pseudocode.md in each folder. Every program was compiled, run and tested against Python’s math.comb for every row from 1 to 30.
Element: Brute
R1 Brute: the number at (row, col) with factorials
n = row - 1 ; r = col - 1
return n! / ( r! * (n - r)! )
Dry run (5, 3): n = 4, r = 2, n - r = 2 -> 24 / (2 * 2) = 6.
Why not: the factorials overflow long before the answer does. int breaks at 13!, long at 21!, so (22, 2), whose answer is 21, prints -1 in Java. Python’s integers never overflow, but the numbers get huge.
Complexity: O(row) time, O(1) extra space. The time is fine; the numbers are the problem.
import java.util.*;
public class PascalElementBrute {
// Brute force: n C r with factorials. Correct on paper, but factorials overflow fast.
// int breaks at 13!, long breaks at 21! (so row 22 already gives a wrong answer).
static long factorial(int n) {
long result = 1;
for (int factor = 2; factor <= n; factor++) {
result = result * factor;
}
return result;
}
static long pascalElementBrute(int row, int col) {
long top = factorial(row - 1);
long bottom = factorial(col - 1) * factorial(row - col);
return top / bottom;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(pascalElementBrute(5, 3)));
System.out.println(show(pascalElementBrute(1, 1)));
System.out.println(show(pascalElementBrute(6, 3)));
System.out.println(show(pascalElementBrute(21, 11)));
}
}#include <bits/stdc++.h>
using namespace std;
// Brute force: n C r with factorials. Correct on paper, but factorials overflow fast.
// int breaks at 13!, long long breaks at 21! (so row 22 already gives a wrong answer).
long long factorial(int n) {
long long result = 1;
for (int factor = 2; factor <= n; factor++) {
result = result * factor;
}
return result;
}
long long pascalElementBrute(int row, int col) {
long long top = factorial(row - 1);
long long bottom = factorial(col - 1) * factorial(row - col);
return top / bottom;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 5; auto arg1 = 3; cout << show(pascalElementBrute(arg0, arg1)) << endl; }
{ auto arg0 = 1; auto arg1 = 1; cout << show(pascalElementBrute(arg0, arg1)) << endl; }
{ auto arg0 = 6; auto arg1 = 3; cout << show(pascalElementBrute(arg0, arg1)) << endl; }
{ auto arg0 = 21; auto arg1 = 11; cout << show(pascalElementBrute(arg0, arg1)) << endl; }
return 0;
}import json
# Brute force: n C r with factorials.
# Python integers never overflow, so this stays correct, but the numbers get huge and slow.
def factorial(n):
result = 1
for factor in range(2, n + 1):
result = result * factor
return result
def pascal_element_brute(row, col):
top = factorial(row - 1)
bottom = factorial(col - 1) * factorial(row - col)
return top // bottom
if __name__ == "__main__":
print(json.dumps(pascal_element_brute(5, 3)).replace(',', ', '))
print(json.dumps(pascal_element_brute(1, 1)).replace(',', ', '))
print(json.dumps(pascal_element_brute(6, 3)).replace(',', ', '))
print(json.dumps(pascal_element_brute(21, 11)).replace(',', ', '))// Brute force: n C r with factorials.
// JavaScript numbers are doubles: factorials lose exactness long before they run out of range.
function factorial(n) {
let result = 1;
for (let factor = 2; factor <= n; factor++) {
result = result * factor;
}
return result;
}
function pascalElementBrute(row, col) {
const top = factorial(row - 1);
const bottom = factorial(col - 1) * factorial(row - col);
return Math.floor(top / bottom);
}
console.log(JSON.stringify(pascalElementBrute(5, 3)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElementBrute(1, 1)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElementBrute(6, 3)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElementBrute(21, 11)).replace(/,/g, ', '));Element: Optimal
R1 Optimal: the number at (row, col), never a factorial
ans = 1
for step from 1 to col - 1:
ans = ans * (row - step) / step (multiply first, then divide)
return ans
Derivation: C(4, 2) = (4 * 3) / (2 * 1). The long factorials cancel, so walk it: x4 / 1, then x3 / 2. Proof the division is exact: after each step, ans = C(row - 1, step), a count of paths, so a whole number. Order matters: (6, 3) is 10; multiply first gives 5 * 4 / 2 = 10, divide first gives 5 / 2 = 2, then 2 * 4 = 8. Dry run (5, 3): step = 1: 1 * 4 / 1 = 4; step = 2: 4 * 3 / 2 = 6; stop -> 6. Column 1: the loop never runs, ans = 1. Symmetry: C(n, r) = C(n, n - r), so you can loop min(col - 1, row - col) steps. (30, 29) = C(29, 1) = 29 in one step. Complexity: O(col) time, O(1) extra space.
import java.util.*;
public class PascalElement {
static long pascalElement(int row, int col) {
long ans = 1;
for (int step = 1; step < col; step++) {
ans = ans * (row - step) / step;
}
return ans;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(pascalElement(5, 3)));
System.out.println(show(pascalElement(1, 1)));
System.out.println(show(pascalElement(6, 3)));
System.out.println(show(pascalElement(30, 15)));
System.out.println(show(pascalElement(31, 16)));
}
}#include <bits/stdc++.h>
using namespace std;
long long pascalElement(int row, int col) {
long long ans = 1;
for (int step = 1; step < col; step++) {
ans = ans * (row - step) / step;
}
return ans;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 5; auto arg1 = 3; cout << show(pascalElement(arg0, arg1)) << endl; }
{ auto arg0 = 1; auto arg1 = 1; cout << show(pascalElement(arg0, arg1)) << endl; }
{ auto arg0 = 6; auto arg1 = 3; cout << show(pascalElement(arg0, arg1)) << endl; }
{ auto arg0 = 30; auto arg1 = 15; cout << show(pascalElement(arg0, arg1)) << endl; }
{ auto arg0 = 31; auto arg1 = 16; cout << show(pascalElement(arg0, arg1)) << endl; }
return 0;
}import json
def pascal_element(row, col):
ans = 1
for step in range(1, col):
ans = ans * (row - step) // step
return ans
if __name__ == "__main__":
print(json.dumps(pascal_element(5, 3)).replace(',', ', '))
print(json.dumps(pascal_element(1, 1)).replace(',', ', '))
print(json.dumps(pascal_element(6, 3)).replace(',', ', '))
print(json.dumps(pascal_element(30, 15)).replace(',', ', '))
print(json.dumps(pascal_element(31, 16)).replace(',', ', '))function pascalElement(row, col) {
let ans = 1;
for (let step = 1; step < col; step++) {
ans = ans * (row - step) / step;
}
return ans;
}
console.log(JSON.stringify(pascalElement(5, 3)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElement(1, 1)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElement(6, 3)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElement(30, 15)).replace(/,/g, ', '));
console.log(JSON.stringify(pascalElement(31, 16)).replace(/,/g, ', '));Row: Optimal
R2 Optimal: one whole row (LeetCode 119 style)
list = [1] ; ans = 1
for col from 1 to row - 1:
ans = ans * (row - col) / col
list.add(ans)
return list
Derivation: the next number is this number x (row - col) / col. Same exactness proof as R1.
Dry run row 5: 1 * 4 / 1 = 4 -> [1, 4]; 4 * 3 / 2 = 6 -> [1, 4, 6]; 6 * 2 / 3 = 4; 4 * 1 / 4 = 1 -> [1, 4, 6, 4, 1]. Row 1: the loop never runs -> [1].
Brute force (not coded): call R1 for every column, O(row^2), because every call repeats the earlier steps.
Overflow: with a 32-bit int, row index 29 still fits (77,558,760 x 15 = 1,163,381,400), but row index 30 breaks (145,422,675 x 16 = 2,326,762,800 > 2,147,483,647), even though its biggest answer, 155,117,520, fits. That is why ans is a long.
Why O(row) and not O(1): the row itself has row numbers.
Complexity: O(row) time, O(1) extra space besides the output.
import java.util.*;
public class GenerateRow {
static List<Integer> generateRow(int row) {
List<Integer> rowList = new ArrayList<>();
rowList.add(1);
long ans = 1;
for (int col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.add((int) ans);
}
return rowList;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(generateRow(5)));
System.out.println(show(generateRow(1)));
System.out.println(show(generateRow(2)));
System.out.println(show(generateRow(7)));
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> generateRow(int row) {
vector<int> rowList;
rowList.push_back(1);
long long ans = 1;
for (int col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.push_back(ans);
}
return rowList;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 5; cout << show(generateRow(arg0)) << endl; }
{ auto arg0 = 1; cout << show(generateRow(arg0)) << endl; }
{ auto arg0 = 2; cout << show(generateRow(arg0)) << endl; }
{ auto arg0 = 7; cout << show(generateRow(arg0)) << endl; }
return 0;
}import json
def generate_row(row):
row_list = [1]
ans = 1
for col in range(1, row):
ans = ans * (row - col) // col
row_list.append(ans)
return row_list
if __name__ == "__main__":
print(json.dumps(generate_row(5)).replace(',', ', '))
print(json.dumps(generate_row(1)).replace(',', ', '))
print(json.dumps(generate_row(2)).replace(',', ', '))
print(json.dumps(generate_row(7)).replace(',', ', '))function generateRow(row) {
const rowList = [1];
let ans = 1;
for (let col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.push(ans);
}
return rowList;
}
console.log(JSON.stringify(generateRow(5)).replace(/,/g, ', '));
console.log(JSON.stringify(generateRow(1)).replace(/,/g, ', '));
console.log(JSON.stringify(generateRow(2)).replace(/,/g, ', '));
console.log(JSON.stringify(generateRow(7)).replace(/,/g, ', '));Triangle: Optimal
R3 Optimal: the whole triangle (LeetCode 118), add the two above
triangle = []
for row from 0 to numRows - 1: (0-indexed loop counters)
rowList = []
for col from 0 to row:
if col == 0 or col == row: rowList.add(1)
else: prev = triangle[row - 1]; rowList.add(prev[col - 1] + prev[col])
triangle.add(rowList)
return triangle
Why the 1s at both ends: an edge cell has only one parent. Pretend there is an invisible zero outside the triangle: 1 + 0 = 1.
Dry run numRows 5: [1]; [1, 1]; [1, 2, 1]; [1, 3, 3, 1]; [1, 4, 6, 4, 1]. numRows 1 -> [[1]] (prev is never touched).
Only additions, so no middle step is ever bigger than the answer (an int is safe up to row index 33).
Complexity: the answer holds n(n+1)/2 numbers (30 rows: 465), so O(n^2) time is the best possible; O(1) extra space besides the output.
import java.util.*;
public class Generate {
static List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int row = 0; row < numRows; row++) {
List<Integer> rowList = new ArrayList<>();
for (int col = 0; col <= row; col++) {
if (col == 0 || col == row) {
rowList.add(1);
} else {
List<Integer> prev = triangle.get(row - 1);
rowList.add(prev.get(col - 1) + prev.get(col));
}
}
triangle.add(rowList);
}
return triangle;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(generate(5)));
System.out.println(show(generate(1)));
System.out.println(show(generate(2)));
}
}#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> generate(int numRows) {
vector<vector<int>> triangle;
for (int row = 0; row < numRows; row++) {
vector<int> rowList;
for (int col = 0; col <= row; col++) {
if (col == 0 || col == row) {
rowList.push_back(1);
} else {
vector<int>& prev = triangle[row - 1];
rowList.push_back(prev[col - 1] + prev[col]);
}
}
triangle.push_back(rowList);
}
return triangle;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 5; cout << show(generate(arg0)) << endl; }
{ auto arg0 = 1; cout << show(generate(arg0)) << endl; }
{ auto arg0 = 2; cout << show(generate(arg0)) << endl; }
return 0;
}import json
def generate(num_rows):
triangle = []
for row in range(num_rows):
row_list = []
for col in range(row + 1):
if col == 0 or col == row:
row_list.append(1)
else:
prev = triangle[row - 1]
row_list.append(prev[col - 1] + prev[col])
triangle.append(row_list)
return triangle
if __name__ == "__main__":
print(json.dumps(generate(5)).replace(',', ', '))
print(json.dumps(generate(1)).replace(',', ', '))
print(json.dumps(generate(2)).replace(',', ', '))function generate(numRows) {
const triangle = [];
for (let row = 0; row < numRows; row++) {
const rowList = [];
for (let col = 0; col <= row; col++) {
if (col === 0 || col === row) {
rowList.push(1);
} else {
const prev = triangle[row - 1];
rowList.push(prev[col - 1] + prev[col]);
}
}
triangle.push(rowList);
}
return triangle;
}
console.log(JSON.stringify(generate(5)).replace(/,/g, ', '));
console.log(JSON.stringify(generate(1)).replace(/,/g, ', '));
console.log(JSON.stringify(generate(2)).replace(/,/g, ', '));Triangle: Row Formula
R3 the other way: build every row with the row formula
for row from 1 to numRows:
triangle.add(generateRow(row)) (R2's formula for each row)
return triangle
Dry run numRows 3: generateRow(1) = [1], generateRow(2) = [1, 1], generateRow(3) = [1, 2, 1].
Complexity: O(n^2) time, the same as adding the two above. It needs a long for the middle steps (see Row-Optimal), which is why the video types the “add the two above” version.
import java.util.*;
public class GenerateByRowFormula {
// LeetCode 118, version (b): build every row with the round two formula.
static List<Integer> generateRow(int row) {
List<Integer> rowList = new ArrayList<>();
rowList.add(1);
long ans = 1;
for (int col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.add((int) ans);
}
return rowList;
}
static List<List<Integer>> generateByRowFormula(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int row = 1; row <= numRows; row++) {
triangle.add(generateRow(row));
}
return triangle;
}
static String show(Object o) {
if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
return String.valueOf(o);
}
public static void main(String[] args) {
System.out.println(show(generateByRowFormula(5)));
System.out.println(show(generateByRowFormula(1)));
System.out.println(show(generateByRowFormula(2)));
}
}#include <bits/stdc++.h>
using namespace std;
// LeetCode 118, version (b): build every row with the round two formula.
vector<int> generateRow(int row) {
vector<int> rowList;
rowList.push_back(1);
long long ans = 1;
for (int col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.push_back(ans);
}
return rowList;
}
vector<vector<int>> generateByRowFormula(int numRows) {
vector<vector<int>> triangle;
for (int row = 1; row <= numRows; row++) {
triangle.push_back(generateRow(row));
}
return triangle;
}
string show(int value) { return to_string(value); }
string show(long long value) { return to_string(value); }
string show(bool value) { return value ? "true" : "false"; }
string show(const string& value) { return "\"" + value + "\""; }
template <typename T> string show(const vector<T>& values) {
string text = "[";
for (size_t index = 0; index < values.size(); index++) {
text += (index ? ", " : "") + show(values[index]);
}
return text + "]";
}
int main() {
{ auto arg0 = 5; cout << show(generateByRowFormula(arg0)) << endl; }
{ auto arg0 = 1; cout << show(generateByRowFormula(arg0)) << endl; }
{ auto arg0 = 2; cout << show(generateByRowFormula(arg0)) << endl; }
return 0;
}import json
# LeetCode 118, version (b): build every row with the round two formula.
def generate_row(row):
row_list = [1]
ans = 1
for col in range(1, row):
ans = ans * (row - col) // col
row_list.append(ans)
return row_list
def generate_by_row_formula(num_rows):
triangle = []
for row in range(1, num_rows + 1):
triangle.append(generate_row(row))
return triangle
if __name__ == "__main__":
print(json.dumps(generate_by_row_formula(5)).replace(',', ', '))
print(json.dumps(generate_by_row_formula(1)).replace(',', ', '))
print(json.dumps(generate_by_row_formula(2)).replace(',', ', '))// LeetCode 118, version (b): build every row with the round two formula.
function generateRow(row) {
const rowList = [1];
let ans = 1;
for (let col = 1; col < row; col++) {
ans = ans * (row - col) / col;
rowList.push(ans);
}
return rowList;
}
function generateByRowFormula(numRows) {
const triangle = [];
for (let row = 1; row <= numRows; row++) {
triangle.push(generateRow(row));
}
return triangle;
}
console.log(JSON.stringify(generateByRowFormula(5)).replace(/,/g, ', '));
console.log(JSON.stringify(generateByRowFormula(1)).replace(/,/g, ', '));
console.log(JSON.stringify(generateByRowFormula(2)).replace(/,/g, ', '));