Pascal's Triangle solution and explanation
Google
TCS
9 more videos on this problem
LeetCode Pascal's Triangle Solution Explained - JavaNick White · 9:20 · 165K views
Pascal's Triangle - Leetcode 118 - PythonNeetCode · 8:41 · 140K views
Pascal's Triangle (LeetCode 118) | Full solution w/ implementation | Fun patterns | Hidden insightsNikhil Lohia · 18:15 · 39K views
Pascals Triangle| Live Coding with Explanation | Leetcode - 118Algorithms Made Easy · 9:55 · 8K views
Pascal’s Triangle | LeetCode 118 | Coding Interview TutorialTerrible Whiteboard · 13:43 · 7K views
LeetCode 118: Pascal's Triangle - Interview Prep Ep 34Fisher Coder · 21:15 · 6K views
LeetCode Problem: 118. Pascal's Triangle | Java SolutionCode for Interview · 16:35 · 5K views
Pascal's Triangle - LeetCode 118 - JavaScriptAlgoJS · 6:42 · 3K views
[Java] Leetcode 118. Pascal's Triangle [Arrays #3]Eric Programming · 6:17 · 1K views
Pascal's Triangle | LeetCode 118 (Easy)Destination FAANG · 13:17 · 1K views
The problem
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1 Output: [[1]]
Constraints:
1 <= numRows <= 30
Approach overview
Problem Overview: Generate the first numRows of Pascal's Triangle. Each number in the triangle equals the sum of the two numbers directly above it. The first and last value of every row is always 1. The output is a 2D array where each inner array represents a row.
Approach 1: Iterative Construction (O(n²) time, O(n²) space)
This method builds the triangle row by row using a dynamic programming idea. Start with the first row [1]. For every new row i, create an array of size i + 1. Set the first and last elements to 1. For the inner elements, compute values using the previous row: row[j] = prevRow[j-1] + prevRow[j]. Continue this process until numRows rows are generated. The algorithm touches each element once, so the total time complexity is O(n²). The triangle itself stores n(n+1)/2 numbers, giving O(n²) space complexity. This approach is straightforward, avoids recursion overhead, and is the most common solution used in production code. It relies heavily on array indexing and sequential iteration, making it a good example of problems involving the Array pattern combined with simple Dynamic Programming.
Approach 2: Recursive Pascal's Triangle Construction (O(n²) time, O(n²) space)
The recursive strategy mirrors the mathematical definition of Pascal's Triangle. Define a function that generates the triangle up to row n. The base case returns [[1]]. For each recursive call, first compute the triangle up to n-1, then construct the new row using the last row of the previously generated triangle. The first and last elements remain 1, while middle elements are computed using adjacent pairs from the previous row. Although recursion makes the logic elegant, the triangle still requires visiting every element, resulting in O(n²) time complexity. The space complexity is also O(n²) for storing the triangle, plus O(n) recursion stack depth. Recursive implementations are useful when practicing recursion patterns or understanding the mathematical structure of Pascal's Triangle, but iterative construction is usually preferred in interviews.
Recommended for interviews: Interviewers typically expect the iterative construction approach. It demonstrates that you understand the relationship between rows and can translate that rule into array operations. Writing the brute recursive version shows conceptual understanding of the triangle's definition, but the iterative Dynamic Programming build is cleaner, avoids stack overhead, and is the solution most candidates present during coding interviews.
Approach 1: Iterative Construction Approach
This approach involves generating Pascal's Triangle row by row using an iterative method. The first row is initialized with [1], and for each subsequent row, the first and last element are always 1. The intermediate elements are calculated as sums of appropriate elements from the previous row.
def generate(numRows):
triangle = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
triangle.append(row)
return triangle
if __name__ == '__main__':
numRows = 5
result = generate(numRows)
for row in result:
print(row)import java.util.ArrayList;
import java.util.List;
public class PascalTriangle {
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
row.add(1);
for (int j = 1; j < i; j++) {
List<Integer> prevRow = triangle.get(i - 1);
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
if (i > 0) row.add(1);
triangle.add(row);
}
return triangle;
}
public static void main(String[] args) {
int numRows = 5;
List<List<Integer>> result = generate(numRows);
for (List<Integer> row : result) {
System.out.println(row);
}
}
}#include <iostream>
#include <vector>
std::vector<std::vector<int>> generate(int numRows) {
std::vector<std::vector<int>> triangle(numRows);
for (int i = 0; i < numRows; i++) {
triangle[i].resize(i + 1);
triangle[i][0] = 1;
triangle[i][i] = 1;
for (int j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
return triangle;
}
int main() {
int numRows = 5;
std::vector<std::vector<int>> result = generate(numRows);
for (const auto& row : result) {
for (int num : row) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}function generate(numRows) {
const triangle = [];
for (let i = 0; i < numRows; i++) {
const row = new Array(i + 1).fill(1);
for (let j = 1; j < i; j++) {
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
triangle.push(row);
}
return triangle;
}
const numRows = 5;
console.log(generate(numRows));#include <stdio.h>
#include <stdlib.h>
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
*returnSize = numRows;
*returnColumnSizes = (int*)malloc(numRows * sizeof(int));
int** triangle = (int**)malloc(numRows * sizeof(int*));
for (int i = 0; i < numRows; i++) {
triangle[i] = (int*)malloc((i + 1) * sizeof(int));
(*returnColumnSizes)[i] = i + 1;
triangle[i][0] = 1;
triangle[i][i] = 1;
for (int j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
return triangle;
}
int main() {
int returnSize;
int* returnColumnSizes;
int numRows = 5;
int** result = generate(numRows, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class PascalTriangle {
public static List<List<int>> Generate(int numRows) {
List<List<int>> triangle = new List<List<int>>();
for (int i = 0; i < numRows; i++) {
List<int> row = new List<int>();
row.Add(1);
for (int j = 1; j < i; j++) {
row.Add(triangle[i - 1][j - 1] + triangle[i - 1][j]);
}
if (i > 0) row.Add(1);
triangle.Add(row);
}
return triangle;
}
public static void Main(String[] args) {
int numRows = 5;
List<List<int>> result = Generate(numRows);
foreach (var row in result) {
Console.WriteLine(string.Join(" ", row));
}
}
}This Python function constructs Pascal's Triangle by initializing each row with 1s, then updating middle values using the sum of two values from the previous row. It returns a list of lists representing the triangle.
Time Complexity: O(numRows^2)
Space Complexity: O(numRows^2)
Approach 2: Recursive Pascal's Triangle Construction
This approach constructs Pascal's Triangle using recursion by calculating each value based on the combination formula. The values on the edges are always 1, and other values are calculated as combinatorial numbers derived recursively.
def combination(n, k):
if k == 0 or k == n:
return 1
return combination(n - 1, k - 1) + combination(n - 1, k)
def generate(numRows):
triangle = []
for i in range(numRows):
row = [combination(i, j) for j in range(i + 1)]
triangle.append(row)
return triangle
if __name__ == '__main__':
numRows = 5
result = generate(numRows)
for row in result:
print(row)import java.util.ArrayList;
import java.util.List;
public class PascalTriangleRecursive {
public static int combination(int n, int k) {
if (k == 0 || k == n) return 1;
return combination(n - 1, k - 1) + combination(n - 1, k);
}
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
row.add(combination(i, j));
}
triangle.add(row);
}
return triangle;
}
public static void main(String[] args) {
int numRows = 5;
List<List<Integer>> result = generate(numRows);
for (List<Integer> row : result) {
System.out.println(row);
}
}
}#include <iostream>
#include <vector>
int combination(int n, int k) {
if (k == 0 || k == n) return 1;
return combination(n - 1, k - 1) + combination(n - 1, k);
}
std::vector<std::vector<int>> generate(int numRows) {
std::vector<std::vector<int>> triangle(numRows);
for (int i = 0; i < numRows; i++) {
triangle[i] = std::vector<int>(i + 1);
for (int j = 0; j <= i; j++) {
triangle[i][j] = combination(i, j);
}
}
return triangle;
}
int main() {
int numRows = 5;
std::vector<std::vector<int>> result = generate(numRows);
for (const auto& row : result) {
for (int value : row) {
std::cout << value << " ";
}
std::cout << std::endl;
}
return 0;
}function combination(n, k) {
if (k === 0 || k === n) return 1;
return combination(n - 1, k - 1) + combination(n - 1, k);
}
function generate(numRows) {
const triangle = [];
for (let i = 0; i < numRows; i++) {
const row = [];
for (let j = 0; j <= i; j++) {
row.push(combination(i, j));
}
triangle.push(row);
}
return triangle;
}
const numRows = 5;
console.log(generate(numRows));#include <stdio.h>
#include <stdlib.h>
int combination(int n, int k) {
if (k == 0 || k == n) return 1;
return combination(n - 1, k - 1) + combination(n - 1, k);
}
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
*returnSize = numRows;
*returnColumnSizes = (int*)malloc(numRows * sizeof(int));
int** triangle = (int**)malloc(numRows * sizeof(int*));
for (int i = 0; i < numRows; i++) {
triangle[i] = (int*)malloc((i + 1) * sizeof(int));
(*returnColumnSizes)[i] = i + 1;
for (int j = 0; j <= i; j++) {
triangle[i][j] = combination(i, j);
}
}
return triangle;
}
int main() {
int returnSize;
int* returnColumnSizes;
int numRows = 5;
int** result = generate(numRows, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class PascalTriangleRecursive {
public static int Combination(int n, int k) {
if (k == 0 || k == n) return 1;
return Combination(n - 1, k - 1) + Combination(n - 1, k);
}
public static List<List<int>> Generate(int numRows) {
List<List<int>> triangle = new List<List<int>>();
for (int i = 0; i < numRows; i++) {
List<int> row = new List<int>();
for (int j = 0; j <= i; j++) {
row.Add(Combination(i, j));
}
triangle.Add(row);
}
return triangle;
}
public static void Main(string[] args) {
int numRows = 5;
List<List<int>> result = Generate(numRows);
foreach (var row in result) {
Console.WriteLine(string.Join(" ", row));
}
}
}In Python, a combination function computes each element of the triangle recursively using combinatorial logic. Each call calculates a combination's value, rapidly constructing Pascal's Triangle row by row.
Time Complexity: O(numRows^3)
Space Complexity: O(numRows^2)
Approach 3: Simulation
We first create an answer array f, then set the first row of f to [1]. Next, starting from the second row, the first and last elements of each row are 1, and for other elements f[i][j] = f[i - 1][j - 1] + f[i - 1][j].
The time complexity is O(n^2), where n is the given number of rows. Ignoring the space consumption of the answer, the space complexity is O(1).
function generate(numRows: number): number[][] {
const f: number[][] = [[1]];
for (let i = 0; i < numRows - 1; ++i) {
const g: number[] = [1];
for (let j = 1; j < f[i].length; ++j) {
g.push(f[i][j - 1] + f[i][j]);
}
g.push(1);
f.push(g);
}
return f;
}func generate(numRows int) [][]int {
f := [][]int{[]int{1}}
for i := 0; i < numRows-1; i++ {
g := []int{1}
for j := 1; j < len(f[i]); j++ {
g = append(g, f[i][j-1]+f[i][j])
}
g = append(g, 1)
f = append(f, g)
}
return f
}impl Solution {
pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
let mut f = vec![vec![1]];
for i in 1..num_rows {
let mut g = vec![1];
for j in 1..f[i as usize - 1].len() {
g.push(f[i as usize - 1][j - 1] + f[i as usize - 1][j]);
}
g.push(1);
f.push(g);
}
f
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Construction Approach | Time Complexity: O(numRows^2) |
| Recursive Pascal's Triangle Construction | Time Complexity: O(numRows^3) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Construction (Dynamic Programming) | O(n²) | O(n²) | Best general solution. Simple loops, no recursion overhead, commonly expected in interviews. |
| Recursive Pascal Construction | O(n²) | O(n²) + O(n) stack | Useful for understanding the mathematical recurrence or practicing recursion patterns. |
Frequently asked questions
Is Pascal's Triangle easy or hard?
Pascal's Triangle is considered an easy problem on most coding platforms. The challenge is recognizing the relationship between adjacent rows and implementing the row-by-row construction correctly using arrays.
How to solve Pascal's Triangle in O(n)?
Producing the full triangle cannot be done in O(n) because the output itself contains O(n^2) numbers. However, generating a single row can be done in O(n) time using combinatorial formulas or incremental updates based on binomial coefficients.
What is the best approach for Pascal's Triangle?
The iterative construction approach using dynamic programming is the most practical solution. Build the triangle row by row and compute each inner value as the sum of the two numbers above it. This method runs in O(n^2) time and uses O(n^2) space to store the triangle, which is optimal since all elements must be generated.
What data structure is used in Pascal's Triangle?
The typical implementation uses a 2D array or a list of lists to store rows of the triangle. Each row is built using values from the previous row, which makes it a simple dynamic programming problem built on top of array indexing.
What is the time complexity of Pascal's Triangle?
Generating the first n rows requires computing n(n+1)/2 elements. Every element is calculated once, so the time complexity is O(n^2). Both iterative and recursive approaches share the same complexity because they must construct the entire triangle.
Pascal's Triangle Python or Java solution approach?
Both Python and Java implementations follow the same idea: iterate from row 0 to numRows-1, initialize each row with 1s at the edges, and compute middle values using the previous row. The algorithm runs in O(n^2) time and stores the result in a list of arrays or lists.
Is Pascal's Triangle asked at Google, Amazon, or Meta interviews?
Pascal's Triangle appears frequently in coding interviews at large tech companies and is common in early interview rounds. It tests array manipulation, understanding of recurrence relations, and basic dynamic programming concepts rather than advanced algorithms.