Pascal's Triangle II: Single Row in O(k) Space

Given an integer rowIndex, return the rowIndex-th (0-indexed) row of Pascal's triangle. For example, rowIndex = 3 returns [1, 3, 3, 1].

This is LeetCode 119: Pascal's Triangle II, and the follow-up asks you to optimize to O(rowIndex) space. That constraint turns a simple construction problem into a lesson on in-place dynamic programming with reverse iteration, a pattern that appears in knapsack problems, rolling DP, and anywhere you need to update an array without corrupting values you still depend on.

Why this problem matters

In Pascal's Triangle (LeetCode 118), you return all rows. Here you only need one. Storing the entire triangle wastes space. The challenge is computing a single row using only that row's worth of memory.

The trick is updating the row in place, but doing it in the right direction. If you update left to right, you overwrite values that later positions still need. Updating right to left avoids that entirely. This same principle shows up in the 1D knapsack optimization and any problem where you collapse a 2D DP table into a single array.

The approach

Start with an array of rowIndex + 1 ones. This represents the skeleton of your target row, since every row in Pascal's triangle begins and ends with 1.

Then simulate building row 1, row 2, ..., up to the target row. For each pass, iterate through the interior positions from right to left, and add each element's left neighbor to itself: row[j] += row[j - 1].

Why right to left? Consider what happens if you go left to right. When you update row[1], its value changes. Then when you try to update row[2], you would use the already-modified row[1] instead of the original. Going right to left means every value you read at row[j - 1] has not been touched yet during this pass.

Building row 3 step by step

Let's trace through rowIndex = 3 to see the in-place updates in action.

After three passes, the row holds [1, 3, 3, 1], which is exactly row 3 of Pascal's triangle. At no point did you need to store any other row. The single array did all the work.

The solution

def getRow(rowIndex):
    row = [1] * (rowIndex + 1)

    for i in range(1, rowIndex + 1):
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]

    return row

Walkthrough

Here is what happens for rowIndex = 3:

• Initialization: row = [1, 1, 1, 1].
• i = 1: inner loop runs for j in range(0, 0, -1), which is empty. Row stays [1, 1, 1, 1].
• i = 2: inner loop runs for j = 1. row[1] += row[0] makes row[1] = 2. Row is now [1, 2, 1, 1].
• i = 3: inner loop runs for j = 2 then j = 1. First, row[2] += row[1] gives 1 + 2 = 3. Then row[1] += row[0] gives 2 + 1 = 3. Row is now [1, 3, 3, 1].

Return [1, 3, 3, 1].

Complexity analysis

Time: O(k^2) where k is rowIndex. The outer loop runs k times, and the inner loop runs up to k - 1 times. Total operations are roughly 1 + 2 + ... + (k-1) = k(k-1)/2, which is O(k^2).

Space: O(k) for the single output array of length k + 1. No additional data structures are needed beyond the row itself.

This meets the follow-up challenge. You cannot do better on space since you need to return a row of k + 1 elements. The time complexity also cannot improve because you need to compute every element, and each pass through the row depends on the previous pass.

The building blocks

This problem is built on one key pattern: in-place DP with reverse iteration.

The idea is that you have an array representing one "layer" of a DP computation, and you want to update it in place to represent the next layer. The catch is that new values depend on old values. If you update from left to right, earlier updates corrupt the data that later updates need. Reverse iteration solves this because each position reads from values that have not been modified yet in the current pass.

This building block appears in several important problems:

• 0/1 Knapsack: the classic DP optimization collapses a 2D table dp[i][w] into a 1D array dp[w] by iterating weights from right to left, exactly the same reason as here.
• Coin Change (LeetCode 322): when optimizing space, you update a 1D DP array. The iteration direction depends on whether items can be reused.
• Unique Paths (LeetCode 62): the 2D grid can be solved with a single row updated left to right (because the dependency direction is different), but the principle of collapsing a 2D table into 1D is the same.

Recognizing "I need to update in place, so I should iterate in the direction that preserves values I still need" is a transferable skill that applies far beyond this problem.

Edge cases

• rowIndex = 0: return [1]. The inner loop never runs, and the initial array [1] is already correct.
• rowIndex = 1: return [1, 1]. The inner loop for i = 1 produces range(0, 0, -1), which is empty. The array [1, 1] is unchanged.
• Large rowIndex: the algorithm handles rowIndex = 33 (the LeetCode constraint) with no issues. The values fit in 32-bit integers since Pascal's triangle row 33 peaks at C(33, 16) = 1,166,803,110.

From understanding to recall

You have traced through the in-place update and seen why right-to-left iteration is essential. The logic makes sense now. But in an interview, you will need to remember the iteration direction, the loop bounds (range(i - 1, 0, -1)), and the initialization ([1] * (rowIndex + 1)). Those details are easy to forget if you only see them once.

Spaced repetition bridges that gap. You revisit this problem at increasing intervals, each time writing the nested loop from scratch and getting the direction right. After a few repetitions, the in-place reverse iteration pattern becomes automatic, and you will recognize it instantly in knapsack and other space-optimized DP problems.

The in-place DP with reverse iteration pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Pascal's Triangle - The predecessor problem where you build the full triangle row by row
• Climbing Stairs - The simplest DP problem, teaching the same "build from previous values" idea