Pascal's Triangle II solution and explanation
Google
9 more videos on this problem
Pascal's Triangle ii | LeetCode 119 | C++, Java, PythonKnowledge Center · 14:07 · 29K views
Pascal's Triangle II - Leetcode 119 - PythonNeetCodeIO · 7:02 · 19K views
Pascal's Triangle II | LeetCode 119 | Coding Interview TutorialTerrible Whiteboard · 12:51 · 6K views
LeetCode 119: Pascal's Triangle II - Interview Prep Ep 28Fisher Coder · 35:04 · 4K views
Unlocking 119. Pascal's Triangle II: The Elegance of Mathematics in Coding in PythonvanAmsen · 5:08 · 3K views
119. Pascal's Triangle II - LeetCode Python tutorialCode with Carter · 11:23 · 566 views
💻Solving All LeetCode Problems with PYTHON 🐍 - 119 Pascal's Triangle IIAlex Brou · 21:06 · 499 views
119. Pascal's Triangle II | Leetcode | Arrays | FundamentalsCoding with Tamilarasan · 4:46 · 469 views
Leetcode 119 | Pascal's Triangle II | Java Solution | 16th Oct 2023Hog Rider · 9:42 · 437 views
Daily Leetcode #1294: Oct 16, 2023 - 119. Pascal's Triangle IIProgramming Live with Larry · 8:38 · 310 views
The problem
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 as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
Approach overview
Problem Overview: Given an integer rowIndex, return the exact row from Pascal’s Triangle. Each element is the sum of the two numbers directly above it, and the first and last values of every row are always 1. The challenge is to compute the requested row efficiently without building unnecessary rows.
Approach 1: Iterative Dynamic Programming (O(n2) time, O(n) space)
This approach builds the row iteratively using the same recurrence rule that defines Pascal’s Triangle. Start with a list initialized to zeros with length rowIndex + 1, set the first element to 1, and update values row by row. To avoid overwriting values you still need, iterate from right to left: row[j] = row[j] + row[j-1]. This works because each update uses values from the previous iteration state. The algorithm runs a nested loop where the outer loop represents rows and the inner loop updates elements within the row, giving O(n^2) time and O(n) space.
This method directly mirrors the recurrence relation and is easy to reason about in interviews. It’s a classic example of space-optimized dynamic programming using a single array instead of a full 2D triangle. The row is treated like a rolling DP state.
Approach 2: Combinatorial Approach (O(n) time, O(1) extra space)
Each value in Pascal’s Triangle corresponds to a binomial coefficient: C(n, k). The kth element in row n equals n! / (k! * (n-k)!). Instead of computing factorials directly, use the recurrence between consecutive coefficients: C(n, k) = C(n, k-1) * (n - k + 1) / k. Start with 1 for C(n,0), then iteratively compute the next coefficient using the previous value.
This produces the entire row in a single pass. Because each element is derived from the previous one using constant-time arithmetic, the algorithm runs in O(n) time and uses only the output array, resulting in O(1) extra space. The approach relies on mathematical properties of combinations and works well when you recognize the binomial pattern inside the array output.
The combinatorial method is the most efficient solution and avoids nested loops entirely. It’s common in competitive programming and shows strong understanding of the underlying mathematics.
Recommended for interviews: Start by explaining the iterative DP solution because it clearly demonstrates the Pascal recurrence and space optimization. Then mention the combinatorial formula as the optimal improvement. Interviewers typically expect the DP reasoning first, but the O(n) combinatorial approach shows deeper insight and stronger algorithmic maturity.
Approach 1: Iterative Approach
The iterative approach builds each row of Pascal's Triangle from the topmost row down to the target row, updating values in-place. The key observation is that each element at position j in a row is the sum of the element at position j and j-1 from the previous row. By starting from the end of the row, you can use the same array for updating values without overwriting the necessary data.
def getRow(rowIndex):
row = [0] * (rowIndex + 1)
row[0] = 1
for i in range(1, rowIndex + 1):
for j in range(i, 0, -1):
row[j] += row[j - 1]
return row
print(getRow(3))import java.util.ArrayList;
import java.util.List;
public class PascalTriangle {
public static List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
for (int i = 0; i <= rowIndex; i++) {
row.add(0);
}
row.set(0, 1);
for (int i = 1; i <= rowIndex; i++) {
for (int j = i; j > 0; j--) {
row.set(j, row.get(j) + row.get(j - 1));
}
}
return row;
}
public static void main(String[] args) {
List<Integer> result = getRow(3);
System.out.println(result);
}
}#include <iostream>
#include <vector>
std::vector<int> getRow(int rowIndex) {
std::vector<int> row(rowIndex + 1, 0);
row[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
for (int j = i; j > 0; --j) {
row[j] += row[j - 1];
}
}
return row;
}
int main() {
int rowIndex = 3;
std::vector<int> result = getRow(rowIndex);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}function getRow(rowIndex) {
let row = new Array(rowIndex + 1).fill(0);
row[0] = 1;
for (let i = 1; i <= rowIndex; i++) {
for (let j = i; j > 0; j--) {
row[j] += row[j - 1];
}
}
return row;
}
console.log(getRow(3));#include <stdio.h>
#include <stdlib.h>
int* getRow(int rowIndex, int* returnSize) {
*returnSize = rowIndex + 1;
int* row = (int*)malloc(sizeof(int) * (*returnSize));
row[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
for (int j = i; j > 0; --j) {
row[j] = row[j] + row[j - 1];
}
}
return row;
}
int main() {
int returnSize;
int* result = getRow(3, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> GetRow(int rowIndex) {
List<int> row = new List<int>(new int[rowIndex + 1]);
row[0] = 1;
for (int i = 1; i <= rowIndex; i++) {
for (int j = i; j > 0; j--) {
row[j] = row[j] + row[j - 1];
}
}
return row;
}
public static void Main() {
Solution sol = new Solution();
var result = sol.GetRow(3);
Console.WriteLine(string.Join(", ", result));
}
}This Python implementation uses a list initialized with zeroes. It applies in-place updates for calculating the values based on Pascal's Triangle properties.
Time Complexity: O(n^2).
Space Complexity: O(n).
Approach 2: Combinatorial Approach
This approach utilizes the combinatorial formula for a specific row in Pascal's Triangle. Specifically, the k-th element in the n-th row is given by the binomial coefficient: C(n, k) = n! / (k! * (n-k)!). Using this fact, we can derive all the values of the row without constructing the triangle iteratively.
def getRow(rowIndex):
row = [1]
C = 1
for i in range(1, rowIndex + 1):
C = C * (rowIndex - i + 1) // i
row.append(C)
return row
print(getRow(3))import java.util.ArrayList;
import java.util.List;
public class PascalTriangle {
public static List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
long C = 1;
row.add((int)C);
for (int i = 1; i <= rowIndex; ++i) {
C = C * (rowIndex - i + 1) / i;
row.add((int)C);
}
return row;
}
public static void main(String[] args) {
List<Integer> result = getRow(3);
System.out.println(result);
}
}#include <iostream>
#include <vector>
class Solution {
public:
std::vector<int> getRow(int rowIndex) {
std::vector<int> row(rowIndex + 1, 1);
long long C = 1;
for (int i = 1; i < rowIndex; ++i) {
C = C * (rowIndex - i + 1) / i;
row[i] = C;
}
return row;
}
};
int main() {
Solution sol;
std::vector<int> result = sol.getRow(3);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}function getRow(rowIndex) {
let row = [1];
let C = 1;
for (let i = 1; i <= rowIndex; i++) {
C = C * (rowIndex - i + 1) / i;
row.push(C);
}
return row;
}
console.log(getRow(3));#include <stdio.h>
#include <stdlib.h>
long long binomialCoeff(int n, int k) {
long long res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
int* getRow(int rowIndex, int* returnSize) {
*returnSize = rowIndex + 1;
int* row = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i <= rowIndex; ++i) {
row[i] = (int)binomialCoeff(rowIndex, i);
}
return row;
}
int main() {
int returnSize;
int* result = getRow(3, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> GetRow(int rowIndex) {
IList<int> row = new List<int> { 1 };
long C = 1;
for (int i = 1; i <= rowIndex; i++) {
C = C * (rowIndex - i + 1) / i;
row.Add((int)C);
}
return row;
}
public static void Main() {
Solution sol = new Solution();
var result = sol.GetRow(3);
Console.WriteLine(string.Join(", ", result));
}
}This Python approach exploits the combinatorial identity for binomial coefficients. Python's native integers support arbitrary precision, making this solution robust over different input sizes.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Recursion
We create an array f of length rowIndex + 1, initially all elements are 1.
Next, starting from the second row, we calculate the value of the jth element in the current row from back to front, f[j] = f[j] + f[j - 1], where j \in [1, i - 1].
Finally, return f.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the given number of rows.
function getRow(rowIndex: number): number[] {
const f: number[] = Array(rowIndex + 1).fill(1);
for (let i = 2; i < rowIndex + 1; ++i) {
for (let j = i - 1; j; --j) {
f[j] += f[j - 1];
}
}
return f;
}func getRow(rowIndex int) []int {
f := make([]int, rowIndex+1)
for i := range f {
f[i] = 1
}
for i := 2; i < rowIndex+1; i++ {
for j := i - 1; j > 0; j-- {
f[j] += f[j-1]
}
}
return f
}impl Solution {
pub fn get_row(row_index: i32) -> Vec<i32> {
let n = (row_index + 1) as usize;
let mut f = vec![1; n];
for i in 2..n {
for j in (1..i).rev() {
f[j] += f[j - 1];
}
}
f
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n^2). |
| Combinatorial Approach | Time Complexity: O(n). |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Dynamic Programming | O(n^2) | O(n) | When explaining Pascal's Triangle recurrence or when mathematical insight is not required. |
| Combinatorial (Binomial Coefficients) | O(n) | O(1) extra | When optimizing for linear time and minimal space using the binomial coefficient relationship. |
Frequently asked questions
Is Pascal's Triangle II easy or hard?
Pascal's Triangle II is classified as an Easy problem. The DP approach is straightforward once you understand the triangle recurrence, while the combinatorial optimization adds a slightly deeper mathematical insight.
Pascal's Triangle II Python/Java solution
Python and Java implementations usually follow the same logic: either update a list in reverse order for the DP approach or compute binomial coefficients iteratively for the O(n) combinatorial solution.
How to solve Pascal's Triangle II in O(n)?
Use the binomial coefficient relationship between consecutive elements. Start with 1 for C(n,0), then compute the next value using C(n,k) = C(n,k-1) * (n-k+1) / k. This produces the entire row sequentially in a single loop.
What is the best approach for Pascal's Triangle II?
The combinatorial approach using binomial coefficients is the most efficient. Each element in row n is C(n, k), which can be computed from the previous coefficient using C(n, k) = C(n, k-1) * (n-k+1) / k. This generates the entire row in O(n) time with O(1) extra space.
Is Pascal's Triangle II asked at Google/Amazon/Meta?
Pascal's Triangle variations frequently appear in interviews at companies like Amazon, Google, and Meta because they test dynamic programming fundamentals, mathematical reasoning, and space optimization techniques.
What data structure is used in Pascal's Triangle II?
The solution typically uses a single array or list to store the current row. In the dynamic programming approach, the array is updated from right to left to preserve values from the previous state.
What is the time complexity of Pascal's Triangle II?
The common dynamic programming solution runs in O(n^2) time because each row requires updating multiple elements. The optimized combinatorial solution computes each element once and runs in O(n) time.