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.
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.
This C program achieves the solution using in-place updates for constructing Pascal's Triangle. It manages memory dynamically and prints the resulting row for a given rowIndex.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) where n is rowIndex as it involves nested iteration to build each row.
Space Complexity: O(n) for storing the result row.
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.
In this C solution, a helper function calculates binomial coefficients using combinatorial properties, avoiding overflow by working iteratively.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n) for storing the row.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n^2) where n is |
| Combinatorial Approach | Time Complexity: O(n). |
| 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 |
Pascal Triangle | Finding nCr in minimal time • take U forward • 374,750 views views
Watch 9 more video solutions →Practice Pascal's Triangle II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor