Pascal's Triangle II

Pascal's Triangle II

What is this problem about?

Pascal's Triangle II asks for only the rowIndex-th row of Pascal's triangle (0-indexed) using O(rowIndex) extra space. The space constraint requires computing the row without storing all previous rows. This easy coding problem tests space-efficient DP computation. The array and dynamic programming interview pattern with space optimization is demonstrated.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this to test whether candidates can apply the O(k) space optimization: updating the row array in-place from right to left. This directly relates to 0/1 knapsack space optimization.

Algorithmic pattern used

In-place right-to-left update. Initialize row = [1]. For each level i from 1 to rowIndex: append 1 to row (now length i+1). Update from right to left (j from i-1 down to 1): row[j] += row[j-1]. After rowIndex steps, return row.

Alternative: Use the combinatorial formula row[j] = row[j-1] * (rowIndex-j+1) / j to compute each entry from left to right in O(k) time without storing previous rows.

Example explanation

rowIndex=3. Steps:

• Start: [1]. Append 1: [1,1]. Update: [1,1].
• Append 1: [1,1,1]. Update (right to left): row[1]+=row[0]=2. [1,2,1].
• Append 1: [1,2,1,1]. Update: row[2]+=row[1]=3, row[1]+=row[0]=3. [1,3,3,1]. Result: [1,3,3,1].

Common mistakes candidates make

• Left-to-right update (corrupts values for subsequent calculations).
• Not appending 1 before updating each level.
• Off-by-one: rowIndex=0 returns [1], rowIndex=1 returns [1,1].
• Forgetting the in-place update trick and using O(n²) space.

Interview preparation tip

The right-to-left DP update is a crucial space optimization technique. It prevents a value from being updated before its "old" version is used for another calculation. This same technique is used in 0/1 knapsack, subset sum, and change-making DP optimizations. Mastering it here makes you fluent for all O(1D space) DP problems in interviews.