Log inSign up
easyLeetCodeNot Started

Pascal's Triangle

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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: `` 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Example 1 · 5 Rows of Pascal's Triangle:

Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation: Row 0: [1] Row 1: [1, 1] Row 2: [1, 1+1, 1] = [1, 2, 1] Row 3: [1, 1+2, 2+1, 1] = [1, 3, 3, 1] Row 4: [1, 1+3, 3+3, 3+1, 1] = [1, 4, 6, 4, 1]

Example 2 · Single Row:

Input: numRows = 1
Output: [[1]]
Explanation: For numRows = 1, only the apex row [1] is generated.

Constraints:

  • 1 <= numRows <= 30

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D dynamic arrays / lists (vector<vector<int>>, List<List<Integer>>, nested lists)
  • Nested loops for triangular iteration
  • Basic recurrence relations

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master iterative bottom-up table construction in 2D jagged arrays.
  • Formulate recurrence relation dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
  • Recognize the connection to binomial expansion and combinations C(n, k).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generating combinations or binomial coefficients C(n, k) row by row.
  • Each row depends directly on the values computed in the previous row.
  • Triangular DP table where row r has length r + 1.

Algorithmic Decision Tree:

  • When constructing Pascal's triangle: Initialize each row with 1s at endpoints, and fill inner elements using row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j].

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Individual Cell Combinations Formula (nCr)

Intuition

Compute each cell triangle[r][c] independently using the factorial combinatorial formula nCr.

Algorithm

  1. 1. For each row r from 0 to numRows - 1: - For each col c from 0 to r: - Compute cell value via combination nCr(r, c). - Add row to triangle.
  2. 2. Return triangle.

Combinations Formula nCr Trace for numRows = 5

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — Setup & Combinations Principle: For numRows = 5, every cell (r, c) is calculated independently using combinations formula nCr = r
Visual state
Values and pointers at this exact step
pascal
r=0
1
r=1
1
1
r=2
1
2
1
r=3
1
—
—
—
Variables at this step
Active Row
r = 3
Cell Index
0
Formula
3C0
Calculated Value
1
Row So Far
[1]
Check / comparison
r = 3, evaluating cell c = 0.
Decision / next transition
Calculate 3C0 = 3! / (0! * 3!) = 1. Insert into row.
Why this step matters

Phase 1 — Setup & Combinations Principle: For numRows = 5, every cell (r, c) is calculated independently using combinations formula nCr = r! / (c! * (r - c)!). We trace constructing the 4th row (r = 3, target 4 elements).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 long long nCr(int n, int r) {
8 long long res = 1;
9 for (int i = 0; i < r; ++i) {
10 res = res * (n - i);
11 res = res / (i + 1);
12 }
13 return res;
14 }
15public:
16 vector<vector<int>> generate(int numRows) {
17 vector<vector<int>> res;
18 for (int r = 0; r < numRows; ++r) {
19 vector<int> row;
20 for (int c = 0; c <= r; ++c) {
21 row.push_back(nCr(r, c));
22 }
23 res.push_back(row);
24 }
25 return res;
26 }
27};
28
29int main() {
30 Solution sol;
31 int numRows = 5;
32 vector<vector<int>> result = sol.generate(numRows);
33
34 cout << "Pascal's Triangle (numRows = " << numRows << "):" << endl;
35 for (const auto& row : result) {
36 cout << "[";
37 for (size_t i = 0; i < row.size(); ++i) {
38 cout << row[i] << (i + 1 < row.size() ? ", " : "");
39 }
40 cout << "]" << endl;
41 }
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N^3) — Computing nCr for each cell takes O(N). Sum of cells is O(N2), so total time is O(N3).
  • Space complexity: O(1) — Auxiliary space is O(1) beyond output matrix.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Row-by-Row DP with Dynamic Auxiliary Row Allocation

Intuition

Construct each row by referencing the preceding row and appending 0s on the flanks.

Algorithm

  1. 1. Initialize triangle = [[1]].
  2. 2. For r from 1 to numRows - 1: - Let prev = triangle[r-1]. - Build new row of size r + 1 where row[0] = 1, row[r] = 1, and row[c] = prev[c-1] + prev[c]. - Append row to triangle.
  3. 3. Return triangle.

Row-by-Row DP with Zero-Padded Adjacent Pair Summing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 2, 1, 0]
Current operationSTEP 1 OF 6
Phase 1 — Setup Padded Sliding Base: To generate row 3, take previous row [1, 2, 1] and pad with virtual zeros at both ends: [0, 1, 2, 1, 0]
Visual state
Values and pointers at this exact step
pascal
r=0
1
r=1
1
1
r=2
1
2
1
r=3
1
—
—
—
Variables at this step
Left Index
0
Right Index
1
Sum
1
New Row
[1]
Check / comparison
L at index 0 (val=0), R at index 1 (val=1).
Decision / next transition
Compute first element: 0 + 1 = 1.
Why this step matters

Phase 1 — Setup Padded Sliding Base: To generate row 3, take previous row [1, 2, 1] and pad with virtual zeros at both ends: [0, 1, 2, 1, 0]. Pointers L and R will sum adjacent pairs.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> generate(int numRows) {
9 vector<vector<int>> res;
10 for (int r = 0; r < numRows; ++r) {
11 vector<int> row(r + 1, 1);
12 for (int c = 1; c < r; ++c) {
13 row[c] = res[r - 1][c - 1] + res[r - 1][c];
14 }
15 res.push_back(row);
16 }
17 return res;
18 }
19};
20
21int main() {
22 Solution sol;
23 int numRows = 5;
24 vector<vector<int>> result = sol.generate(numRows);
25
26 cout << "Pascal's Triangle (numRows = " << numRows << "):" << endl;
27 for (const auto& row : result) {
28 cout << "[";
29 for (size_t i = 0; i < row.size(); ++i) {
30 cout << row[i] << (i + 1 < row.size() ? ", " : "");
31 }
32 cout << "]" << endl;
33 }
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Generates all N*(N+1)/2 cells in O(N2) time.
  • Space complexity: O(N) — Auxiliary space for row buffers is O(N).

3. Direct Multiplicative Row Construction (Optimal & Standard)

Intuition

Generate each row in linear time using the ratio C(n, k) = C(n, k-1) * (n - k + 1) / k.

Algorithm

  1. 1. For each row r from 0 to numRows - 1: - Initialize row of size r + 1 with row[0] = 1. - For k from 1 to r: row[k] = row[k-1] * (r - k + 1) / k. - Append row to result.
  2. 2. Return result.

Direct Multiplicative Row Construction (O(1) Extra Space per Row)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 6, 4, 1]
Current operationSTEP 1 OF 6
Phase 1 — Base Boundary Element: For any row n, the first element (index 0) is always 1
Visual state
Values and pointers at this exact step
pascal
r=0
1
r=1
1
1
r=2
1
2
1
r=3
1
3
3
1
r=4
1
—
—
—
—
Variables at this step
Row Index n
4
Col i
0
ans
1
Formula
Base = 1
Current Row
[1, —, —, —, —]
Check / comparison
i = 0, base element.
Decision / next transition
ans = 1. row[0] = 1.
Why this step matters

Phase 1 — Base Boundary Element: For any row n, the first element (index 0) is always 1. Set ans = 1 and store at index 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 vector<int> generateRow(int r) {
8 long long ans = 1;
9 vector<int> row;
10 row.push_back(1);
11 for (int col = 1; col <= r; ++col) {
12 ans = ans * (r - col + 1) / col;
13 row.push_back(ans);
14 }
15 return row;
16 }
17public:
18 vector<vector<int>> generate(int numRows) {
19 vector<vector<int>> res;
20 for (int r = 0; r < numRows; ++r) {
21 res.push_back(generateRow(r));
22 }
23 return res;
24 }
25};
26
27int main() {
28 Solution sol;
29 int numRows = 5;
30 vector<vector<int>> result = sol.generate(numRows);
31
32 cout << "Pascal's Triangle (numRows = " << numRows << "):" << endl;
33 for (const auto& row : result) {
34 cout << "[";
35 for (size_t i = 0; i < row.size(); ++i) {
36 cout << row[i] << (i + 1 < row.size() ? ", " : "");
37 }
38 cout << "]" << endl;
39 }
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N^2) — Generates all N*(N+1)/2 elements in optimal O(N2) time.
  • Space complexity: O(1) — No auxiliary structures beyond the output triangle. Extra space is O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Individual Cell Combinations Formula (nCr)O(N^3)O(1)Compute each cell triangle[r][c] independently using the factorial combinatorial formula nCr.Repeated redundant scans over the input.
2.Approach 2: Row-by-Row DP with Dynamic Auxiliary Row AllocationO(N^2)O(N)Construct each row by referencing the preceding row and appending 0s on the flanks.Auxiliary memory allocation or sorting step.
3.Approach 3: Direct Multiplicative Row Construction (Optimal & Standard)OptimalO(N^2)O(1)Generate each row in linear time using the ratio C(n, k) = C(n, k-1) * (n - k + 1) / k.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • numRows = 1 — Input: `, Expected: ` —
  • numRows = 2 — Input: `, Expected: ` —
  • numRows = 30 (Max Constraint) — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Pascal's Triangle?

2.Why is the brute force approach suboptimal for large inputs in Pascal's Triangle?

3.Which data structure or technique enables the optimal solution for Pascal's Triangle?

Back to DSA Sheet