Log inSign up
easyLeetCodeNot Started

Pascal's Triangle II

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

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Follow-up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Example 1 · Row Index 3:

Input: rowIndex = 3
Output: [1, 3, 3, 1]
Explanation: The 3rd row (0-indexed) of Pascal's triangle is [1, 3, 3, 1].

Example 2 · Row Index 0 (Apex):

Input: rowIndex = 0
Output: [1]
Explanation: The 0th row is just [1].

Example 3 · Row Index 1:

Input: rowIndex = 1
Output: [1, 1]
Explanation: The 1st row is [1, 1].

Constraints:

  • 0 <= rowIndex <= 33

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Pascal's Triangle fundamentals (row[j] = prev[j-1] + prev[j])
  • Space optimization techniques in Dynamic Programming (rolling arrays)
  • Right-to-left traversal to avoid stale state clobbering

What You'll Learn

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

  • Master DP space optimization from O(K2) down to O(K) using 1D rolling buffers.
  • Understand why reverse (right-to-left) iteration is necessary to avoid overwriting dependencies.
  • Learn the direct multiplicative combination formula nCr = nC(r-1) * (n - r + 1) / r.

Pattern Recognition Trigger

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

Signals to Look For:

  • Need only the last/target row of a recurrence relation without retaining historical rows.
  • DP transition depends solely on the immediately preceding layer: dp[j] = dp[j] + dp[j - 1].
  • Memory constraint requires strictly O(K) space.

Algorithmic Decision Tree:

  • When optimizing 2D DP layer transitions to 1D: Iterate the inner loop backwards from i down to 1 so dp[j - 1] retains its previous-layer value.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Full 2D Pascal Triangle Matrix Construction

Intuition

Generate the entire 2D Pascal Triangle up to rowIndex and return the last row.

Algorithm

  1. 1. Initialize 2D list triangle.
  2. 2. For r from 0 to rowIndex: - Create row of size r + 1 with boundaries set to 1. - For c from 1 to r - 1: row[c] = triangle[r-1][c-1] + triangle[r-1][c]. - Append row to triangle.
  3. 3. Return triangle[rowIndex].

Full 2D Triangle Generation Up to rowIndex = 3

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 — Generate Preceding Row 0 & 1: Brute force builds complete 2D triangle from apex
Visual state
Values and pointers at this exact step
pascal
r=0
1
r=1
1
1
Variables at this step
Current Row
1
Target Row
3
2D Table
[[1], [1, 1]]
Check / comparison
rowIndex = 3, currently at row 1.
Decision / next transition
Store rows 0 and 1. Proceed to row 2.
Why this step matters

Phase 1 — Generate Preceding Row 0 & 1: Brute force builds complete 2D triangle from apex. Row 0 = [1], Row 1 = [1, 1]. Both rows stored in 2D array.

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

Time & Space Complexity

  • Time complexity: O(K^2) — Generates all (K+1)*(K+2)/2 elements across K rows in O(K2) time.
  • Space complexity: O(K^2) — Stores all previous rows, consuming O(K2) memory.

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. 1D In-Place DP (Right-to-Left Update)

Intuition

Maintain a single 1D array of size rowIndex + 1 and update values in reverse from right to left.

Algorithm

  1. 1. Initialize array row of size rowIndex + 1 with row[0] = 1.
  2. 2. For r from 1 to rowIndex: - For c from r down to 1: row[c] = row[c] + row[c-1].
  3. 3. Return row.

1D In-Place DP (Right-to-Left Update to Preserve Preceding State)

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 Single 1D Buffer: Allocate a single array of size rowIndex + 1 = 4
Visual state
Values and pointers at this exact step
array
S
1
0
0
0
0
↑ Init
1
2
3
Variables at this step
Pass i
0
Buffer
[1, 0, 0, 0]
Check / comparison
Buffer size = 4. Only O(k) memory used.
Decision / next transition
row[0] = 1. Begin outer passes from i = 1 to 3.
Why this step matters

Phase 1 — Setup Single 1D Buffer: Allocate a single array of size rowIndex + 1 = 4. Initialize row[0] = 1 and remaining cells to 0: [1, 0, 0, 0].

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

Time & Space Complexity

  • Time complexity: O(K^2) — Nested loops compute K*(K+1)/2 additions in O(K2) time.
  • Space complexity: O(K) — Uses a single 1D array of size K+1, consuming O(K) space.

3. Direct Combinatorial Multiplicative Formula (O(K) Time)

Intuition

Compute each element directly in O(K) linear time using C(n, k) = C(n, k-1) * (n - k + 1) / k.

Algorithm

  1. 1. Initialize array row of size rowIndex + 1 with row[0] = 1.
  2. 2. For k from 1 to rowIndex: - row[k] = (row[k-1] * (rowIndex - k + 1)) / k.
  3. 3. Return row in O(K) time and O(1) auxiliary space.

Direct Combinatorial Multiplicative Formula (O(K) Time & O(1) Space)

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 — Base Element: By definition, row[0] is always 1
Visual state
Values and pointers at this exact step
array
S
1
—
—
—
0
↑ k = 0
1
2
3
Variables at this step
Index k
0
current
1
Formula
row[0] = 1
Array
[1, —, —, —]
Check / comparison
k = 0, base element = 1.
Decision / next transition
row[0] = 1.
Why this step matters

Phase 1 — Base Element: By definition, row[0] is always 1. Set current = 1 and insert at index 0.

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

Time & Space Complexity

  • Time complexity: O(K) — A single loop runs K times performing O(1) multiplication and division.
  • Space complexity: O(1) — Output array does not count toward auxiliary space. 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: Full 2D Pascal Triangle Matrix ConstructionO(K^2)O(K^2)Generate the entire 2D Pascal Triangle up to rowIndex and return the last row.Repeated redundant scans over the input.
2.Approach 2: 1D In-Place DP (Right-to-Left Update)O(K^2)O(K)Maintain a single 1D array of size rowIndex + 1 and update values in reverse from right to left.Auxiliary memory allocation or sorting step.
3.Approach 3: Direct Combinatorial Multiplicative Formula (O(K) Time)OptimalO(K)O(1)Compute each element directly in O(K) linear time using 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:

  • rowIndex = 0 — Input: `, Expected: ` —
  • rowIndex = 1 — Input: `, Expected: ` —
  • rowIndex = 33 (Constraint Bound) — 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 II?

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

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

Back to DSA Sheet