LeetCode 119 – Pascal's Triangle II

Pascal's Triangle asked for the whole triangle, where the output was the complexity and there was nothing to improve. This asks for one row, and adds a follow-up requiring O(k) space — which turns a warm-up into a real exercise in updating an array in place without destroying what you are about to read.

The problem

Given rowIndex, return that row of Pascal's triangle. The row is 0-indexed. The follow-up asks for O(rowIndex) extra space.

rowIndex = 3  -> [1,3,3,1]
rowIndex = 0  -> [1]
rowIndex = 1  -> [1,1]
rowIndex = 4  -> [1,4,6,4,1]

Row k has k + 1 entries, so rowIndex = 3 gives four numbers. Confirm that against the examples before writing anything; it is where the off-by-one lives.

The obvious answer, and the constraint that rules it out

Build the whole triangle as in problem 118 and return the last row. Correct, and O(k²) space for a result of size k. The follow-up exists to rule it out.

Keeping two rows — previous and current — gets you to O(k) and is a perfectly good answer. But one row is enough, and getting there is the point.

Updating in place, backwards

The natural attempt destroys its own inputs:

row = [1, 2, 1]   updating LEFT to RIGHT to get [1, 3, 3, 1]

row[1] = row[1] + row[0] = 3     row is now [1, 3, 1]
row[2] = row[2] + row[1] = 4     WRONG -- row[1] is the NEW 3, not the old 2

Each entry needs the previous row's value at j - 1, and going left to right has already overwritten it. Going right to left fixes it: entries to the left have not been touched yet, so they still hold the previous row's values.

row = [1, 2, 1, 1]   (append the new trailing 1 first)

row[2] = row[2] + row[1] = 1 + 2 = 3     row[1] still the OLD 2
row[1] = row[1] + row[0] = 2 + 1 = 3
                                          -> [1, 3, 3, 1]

This is the same rule as Merge Sorted Array: when the write would clobber something unread, go the other way. Naming that connection is worth more than the solution itself.

Java

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(rowIndex + 1);
        row.add(1);

        for (int i = 1; i <= rowIndex; i++) {
            row.add(1);                       // the new trailing 1

            // Backwards, so row.get(j-1) is still the PREVIOUS row's value.
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }

        return row;
    }
}

The inner loop stops at j > 0, leaving row.get(0) as the leading 1 — it has no above-left neighbour and must not be touched. The trailing 1 was just appended and is already correct, which is why the loop starts at i - 1 rather than i.

rowIndex = 0 skips the outer loop entirely and returns [1]. No guard needed.

Python

class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [1]

        for i in range(1, rowIndex + 1):
            row.append(1)                     # the new trailing 1

            for j in range(i - 1, 0, -1):     # right to left, stopping before index 0
                row[j] += row[j - 1]

        return row

range(i - 1, 0, -1) is the backwards sweep with the leading 1 excluded. Reading a three-argument range correctly under pressure is worth practising — the stop value is exclusive in both directions, which is what keeps index 0 safe.

The closed form

Row n is the binomial coefficients C(n, 0) … C(n, n), and consecutive ones are related:

C(n, k) = C(n, k-1) * (n - k + 1) / k

That gives the row in O(k) time — better than the O(k²) the DP needs — with a real caveat: the intermediate products overflow long before the answers do, and the division is only exact if you multiply first. Reordering it to divide early loses precision and gives wrong integers.

Mention it, note the overflow, and use the DP unless asked. An answer that is asymptotically better and numerically fragile is not automatically the better answer, and saying so is the mature version of knowing the formula.

Complexity

The one-row version uses no space beyond the answer it has to return, which is the strongest form of the follow-up's request. The time stays O(k²) because every row up to k is still computed.

The pattern

Rolling a single array and sweeping in the direction that preserves unread values is one of the most reusable tricks in DP. Unique Paths (62) sweeps forwards because it wants the already-updated neighbour; this sweeps backwards because it wants the stale one. The 0/1 knapsack famously goes backwards for exactly this reason, while unbounded knapsack goes forwards — and that single direction is the entire difference between the two problems.

So the transferable question is not "roll the array?" but "which values does this cell need — the new ones or the old ones?" The answer picks the direction.

What the interviewer is checking

• That row k has k + 1 entries.
• That you notice the follow-up rules out building the whole triangle.
• The backwards sweep, and that you can say what breaks going forwards.
• That index 0 is left alone and the trailing 1 is appended first.
• rowIndex = 0 returning [1].
• That you connect the direction rule to knapsack, or at least to Merge Sorted Array.
• If you offer the closed form, that you raise the overflow with it.