Pascal's Triangle II

Pascal's Triangle II

What is this problem about?

Pascal's Triangle II asks you to return only the k-th row (0-indexed) of Pascal's triangle using O(k) space. Unlike generating all rows, here you only need the final row. This easy coding problem tests space-optimized row computation. The array and dynamic programming interview pattern is demonstrated with a space optimization.

Why is this asked in interviews?

Goldman Sachs and Yahoo ask this to test space optimization of a DP problem. The naive approach builds all k rows, but with careful in-place updating, you can compute the k-th row using only O(k) space.

Algorithmic pattern used

In-place reverse update. Initialize row = [1]. For each step i from 1 to k: update the row in reverse (right to left). For j from i down to 1: row[j] += row[j-1]. This mimics the Pascal's rule in-place without needing a previous row copy.

Example explanation

k=4. Start: [1]. Step 1: add 1 → [1,1]. Step 2: [1,2,1]. Step 3: [1,3,3,1]. Step 4: reverse update → [1,4,6,4,1]. Result: [1,4,6,4,1].

Alternatively: directly compute using C(k,0), C(k,1), ..., C(k,k) = 1, k, k(k-1)/2, ...

Common mistakes candidates make

• Updating left-to-right (causes cascading incorrect updates).
• Using a new array each step (O(k²) space, violates constraint).
• Not starting with a row of length 1.
• Off-by-one in which row is returned (0-indexed vs 1-indexed k).

Interview preparation tip

Pascal's Triangle II is the classic space-optimized DP problem. The reverse-update trick — updating right-to-left to avoid using old values — appears in many 0/1 knapsack optimizations. Practice this trick until it feels natural. Also know the direct formula approach using C(k,j) = C(k,j-1) * (k-j+1) / j, which computes each element in O(1) after the previous one.