Pascal's Triangle II
EasyPrompt
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?
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive definition of Pascal's Triangle, C(n, k) = C(n-1, k-1) + C(n-1, k), into a recursive function. To get the entire rowIndex-th row, we call this function for each column index from 0 to rowIndex.
Algorithm
- Create an empty list
resultto store the row. - Loop with an index
kfrom0torowIndex. - In each iteration, call a recursive helper function,
pascalValue(rowIndex, k), to compute the element at that position. - Add the value returned by the helper function to the
resultlist. - The
pascalValue(row, col)helper function is defined as follows:- Base Case: If
colis0orcolis equal torow, return1. - Recursive Step: Otherwise, return the sum of
pascalValue(row - 1, col - 1)andpascalValue(row - 1, col).
- Base Case: If
Walkthrough
We define a recursive function, say pascalValue(row, col), which computes the value at a specific position in the triangle.
The base cases for the recursion are when col == 0 or col == row, in which case the value is 1.
For any other position (row, col), the value is the sum of pascalValue(row - 1, col - 1) and pascalValue(row - 1, col).
To generate the final result, we create a list and iterate from k = 0 to rowIndex, populating the list with the results of pascalValue(rowIndex, k).
This method is highly inefficient because it recomputes the same values multiple times. For example, calculating the value at (5, 2) and (5, 3) both require computing the value at (4, 2), leading to an exponential number of overlapping subproblems.
class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); for (int k = 0; k <= rowIndex; k++) { row.add(pascalValue(rowIndex, k)); } return row; } private int pascalValue(int row, int col) { if (col == 0 || col == row) { return 1; } // Recursive step return pascalValue(row - 1, col - 1) + pascalValue(row - 1, col); }}Complexity
Time
O(2^rowIndex)
Space
O(rowIndex)
Trade-offs
Pros
Simple to understand as it directly models the mathematical definition of Pascal's Triangle.
Cons
Extremely inefficient due to a massive number of redundant computations.
Will likely result in a 'Time Limit Exceeded' error for even moderately large values of
rowIndex.
Solutions
Solution
class Solution {public List<Integer> getRow(int rowIndex) { List<Integer> f = new ArrayList<>(); for (int i = 0; i < rowIndex + 1; ++i) { f.add(1); } for (int i = 2; i < rowIndex + 1; ++i) { for (int j = i - 1; j > 0; --j) { f.set(j, f.get(j) + f.get(j - 1)); } } return f; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.