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

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:

// Java brute-force boredom
List<Integer> getRow(int rowIndex) {
    List<Integer>[] triangle = new ArrayList[rowIndex + 1];
    for (int i = 0; i <= rowIndex; i++) {
        triangle[i] = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) triangle[i].add(1);
            else triangle[i].add(triangle[i - 1].get(j - 1) + triangle[i - 1].get(j));
        }
    }
    return triangle[rowIndex];
}

🧠 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

• 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.

• For each level (starting at 2):
  

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

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

• 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.

💻 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.

🧠 Interviewer Brain-Tattoo

“Update right-to-left, not because you want to—but because arrays never forget betrayal.”