Watch 10 video solutions for Pascal's Triangle II, a easy level problem involving Array, Dynamic Programming. This walkthrough by take U forward has 374,750 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: Pascal's Triangle is built so each number is the sum of the two numbers directly above it. The task is to return the rowIndex-th row of the triangle (0-indexed) without generating the entire structure.
Approach 1: Iterative Dynamic Programming (O(n²) time, O(n) space)
This approach simulates the triangle row by row using a single array. Start with a list initialized to zeros and set the first value to 1. For every new row, iterate from right to left and update each position using row[j] = row[j] + row[j-1]. Updating from the end prevents overwriting values that are still needed for the current computation. The array gradually evolves into the target row, so you never store the full triangle.
This method directly reflects the recurrence relation of Pascal's Triangle and is a classic dynamic programming pattern. It uses only one array of length rowIndex + 1, making the memory footprint minimal. Since each row update processes up to rowIndex elements and you perform it for every row, the total complexity is O(n²) time with O(n) space.
Approach 2: Combinatorial Formula (O(n) time, O(1) space)
Each element in Pascal's Triangle corresponds to a binomial coefficient. The value at index k in row n equals C(n, k). Instead of computing factorials, compute each value iteratively using the relationship C(n, k) = C(n, k-1) * (n - k + 1) / k. Start with 1 and derive the next element using the previous one.
This avoids recomputing combinations from scratch and produces the entire row in a single pass. Only the previous value is needed, so extra memory usage stays constant aside from the output list. Time complexity is O(n), which is optimal for generating a row of length n + 1.
The combinatorial approach leans more on mathematical insight than standard array iteration. It’s especially useful when interviewers want to see whether you recognize the binomial coefficient pattern in Pascal's Triangle.
Recommended for interviews: Start with the iterative dynamic programming approach. It shows you understand the triangle's construction and how to optimize space by updating the array from right to left. After that, mention the combinatorial formula as the optimal improvement. Interviewers often appreciate seeing both perspectives: DP for clarity and the mathematical approach for efficiency.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Dynamic Programming | O(n²) | O(n) | When demonstrating Pascal's Triangle construction or typical DP state transitions |
| Combinatorial Formula | O(n) | O(1) extra | When optimal performance is required and the binomial coefficient relationship is recognized |