Pascal's Triangle II — Solution

Problem

Pascal's triangle is a number grid where each interior element equals the sum of the two elements directly above it, with every row starting and ending in 1. Given a 0-based row index, return just that one row without storing the entire triangle.

• Input: rowIndex = 3
• Output: [1, 3, 3, 1]
• Explanation: Rows 0 through 3 are [1], [1,1], [1,2,1], [1,3,3,1]; the third row is the answer.

Counter-example: rowIndex = 0 returns [1] — the degenerate base case where the loop runs zero times and the initial array is already correct.

Intuition

Each row is the previous one shifted right by one, then added element-wise to the original. The key observation is that if you scan from right to left, you can apply this update to a single array without needing a second copy — when you add row[j] += row[j-1], the value at j-1 still holds the previous row's value since you haven't touched it yet. Separately, every element at position k in row n is the binomial coefficient C(n, k), which can be computed directly from the previous coefficient in one multiply and one divide — making the entire row computable in O(n) time.

Approach 1 — In-Place Row Update

Initialize a single array of size rowIndex + 1 with row[0] = 1 and the rest zeros. For each simulated row from 1 to rowIndex, scan right to left and add each element to its left neighbor.

1. Allocate row of size rowIndex + 1, set row[0] = 1, all others to 0.
2. Loop i from 1 to rowIndex (each iteration represents building one new row).
3. Inner loop j from i down to 1: row[j] += row[j - 1].
4. Return row.

1def get_row(row_index: int) -> list[int]:
2    row = [0] * (row_index + 1)
3    row[0] = 1  # first element of every row is always 1
4    for i in range(1, row_index + 1):
5        for j in range(i, 0, -1):  # right to left so row[j-1] still holds previous-row value
6            row[j] += row[j - 1]
7    return row

Time: O(n²) — outer loop runs n times, inner loop averages n/2 steps.

Space: O(n) — single array of size rowIndex + 1; no auxiliary storage.

Approach 2 — Binomial Coefficient Formula

Every element at column k of row n equals C(n, k). Rather than computing each from scratch, use the recurrence C(n, k) = C(n, k-1) × (n - k + 1) / k, which lets you derive each coefficient from the previous one in O(1). This runs the whole row in a single O(n) pass.

1. Start with row = [1] and prev = 1 (representing C(n, 0)).
2. Loop k from 1 to rowIndex: compute curr = prev * (rowIndex - k + 1) // k.
3. Append curr to row and update prev = curr.
4. Return row.

1def get_row(row_index: int) -> list[int]:
2    row = [1]
3    prev_coeff = 1
4    for k in range(1, row_index + 1):
5        # C(n, k) = C(n, k-1) * (n - k + 1) / k — always divides evenly since C(n,k) is an integer
6        curr_coeff = prev_coeff * (row_index - k + 1) // k
7        row.append(curr_coeff)
8        prev_coeff = curr_coeff
9    return row

Time: O(n) — single pass, one multiply and one divide per element.

Space: O(n) — output array only; no auxiliary storage.

Complexity Summary

Common Mistakes

• Updating left to right in the DP approach — if you loop j from 1 to i, row[j-1] has already been updated for the current row by the time you compute row[j], producing wrong values. The right-to-left order is essential.
• Inner loop going to j = 0 — row[0] is always 1 and must never change; the inner loop should stop at j = 1 so it never touches the leading 1.
• Integer overflow in the binomial approach — for rowIndex >= 34, the intermediate product prevCoeff * (rowIndex - k + 1) can exceed 2^31 - 1 before the divide. Use long (Java) or long long (C++) for the running coefficient.
• Confusing 0-based rowIndex with 1-based row count — rowIndex = 3 returns the fourth row [1, 3, 3, 1], not the third. Calling the function with rowIndex - 1 when you mean rowIndex is a common off-by-one.
• Returning the full triangle from Pascal's Triangle I — that problem asks for all rows as a list of lists; this problem asks for one specific row. Returning triangle[rowIndex] from a precomputed full triangle is correct, but wasteful when O(n) time suffices.

Related Problems

• Pascal's Triangle — builds the entire triangle instead of a single row; simpler loop structure but O(n²) space
• Combinations — C(n, k) is exactly the kth element of Pascal's row n; same mathematical foundation
• Unique Paths — the answer is the binomial coefficient C(m+n-2, m-1), the same formula used in Approach 2
• Coin Change II — uses a rolling-array DP where updating right to left avoids double-counting, the same directional trick as Approach 1
• Climbing Stairs — simple iterative DP that derives each answer from the previous two; introduces the same "build forward from a small state" pattern