The O(n) Club: Pascal’s Triangle II, or How to Mutate Arrays Without Crying

⚡ TL;DR

Pascals’s Triangle II: You want rowIndex-th row (0-based) of Pascal’s Triangle—without building every layer down to bedrock. Classic rookie move is meekly building every row. Hero move? One array, right-to-left updates. Here’s the tired way:

🧠 How Devs Usually Mess This Up

So many ways to step on a rake here. You might build the whole triangle (RAM-hoarder alert). Or you update left-to-right—which murders the numbers you still need for the next cell. Or, the pièce de résistance: Off-by-one, because apparently every dev needs a reminder that 0-based means rowIndex=3 gets you [1, 3, 3, 1], the fourth row. 🍵

🔍 What’s Actually Going On

Pretend you’re a chef stacking dessert layers, but only the top one matters. Each mid-slice is built from the two spoonfuls below, except the edges—they’re always 1, like raisins in a fruitcake. Instead of hauling the whole cake around, you just keep re-layering the top, updating from the right so you don’t eat your own ingredients. That’s O(n) space, a.k.a. not wasting your arrays or your life.

🛠️ PseudoCode

Right-to-left, update each cell:

for (int j = i - 1; j > 0; j--)
    row.set(j, row.get(j) + row.get(j - 1));

If you go left-to-right, you’re actually building a pyramid of bugs. Right-to-left keeps dependencies untarnished.

For each level (starting at 2):

for (int i = 2; i <= rowIndex; i++) { ... }

No point updating before the second row—nothing to mix.

Prep your plate (array) full of 1s:

List<Integer> row = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));

Why 1s? Edges never change. Less logic, more chill.

💻 The Code

import java.util.*;
 public class PascalsTriangleII {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));
        for (int i = 2; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

Right-to-left or bust: Yes, I’m repeating myself. If you update left-to-right: broken output, silent shame, wasted caffeine.
0-based index confusion: LeetCode wants rowIndex = 3 → [1, 3, 3, 1]. Not 1-based. Tattoo it on your typing hand.
Full triangle trap: Allocating every row? Welcome to O(n^2) misery. Just update one list.
Complexity check: O(n) time, O(n) space. That’s n = rowIndex+1. As snappy as Java gets without time travel.