Pascal's Triangle II - Solution & Explanation

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(n²) 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.