The O(n) Club: Triangle Minimum Path Sum — The Only Pyramid Scheme You’ll Ever Love

The O(n) Club: Triangle Minimum Path Sum — The Only Pyramid Scheme You’ll Ever Love

⚡ TL;DR

Solve a triangle of numbers by finding the cheapest route from top to bottom, moving only to adjacent numbers each row. Don’t try brute-force unless you collect stack overflow errors for sport. Use bottom-up dynamic programming in Java—it’s quick, clear, and sadly earns no frequent flyer miles.

// Minimalist Java DP, bottom-up
int n = triangle.size();
int[] temp = triangle.get(n-1).stream().mapToInt(i->i).toArray();
for (int i = n-2; i >= 0; i--)
  for (int j = 0; j <= i; j++)
    temp[j] = triangle.get(i).get(j) + Math.min(temp[j], temp[j+1]);
return temp[0];

🧠 How Devs Usually Mess This Up

Ah, the classic: you try every path down the triangle. Next thing you know, your code’s exponential and your laptop’s fan just filed for workers’ comp. Or maybe you built a DP table so big you saw OutOfMemoryError for the first time this week? Or you obsessed over storing the actual route, even though the problem just wants the sum. Welcome to the club—we’ve all suffered.

🔍 What’s Actually Going On

Think of the triangle as the world’s saddest buffet: every row adds some calories (cost), and you’re only allowed to eat what’s directly below or diagonally next door. Instead of wandering around, you work from the bottom up, keeping track of the lightest possible guilt at every point. Dynamic programming, for once, makes your life easier instead of harder. Bubble up those minimums and claim your overpriced dessert (the optimal answer) from the top.

🛠️ PseudoCode

• Copy the bottom row: This is your baseline for what it costs to finish from each cell.
• Iterate upwards: For each cell above, update with current + min(leftChild, rightChild).
• Repeat for each row, moving up: Your temp array shrinks the cost at each stage. No need for a second mortgage on your memory.
• Top cell now contains the minimum path sum: Which you get with temp[0]. Java can be nice if you squint.

// Java-ish pseudocode
List<List<Integer>> triangle = ...;
int n = triangle.size();
int[] temp = triangle.get(n-1).stream().mapToInt(i->i).toArray();
for (int row = n-2; row >= 0; row--) {
   for (int col = 0; col <= row; col++) {
      temp[col] = triangle.get(row).get(col) + Math.min(temp[col], temp[col+1]);
   }
}
return temp[0];

💻 The Code

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = triangle.get(n-1).get(i);
    }
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
        }
    }
    return dp[0];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Trying every path blows up exponentially—don’t bother unless you hate time.
• In-place mutation is fine only if the interviewer gives you the green light. Otherwise, play nice and use a separate array.
• Watch negative numbers or triangles with just one row—you’re not being punked, it could happen.
• Space: O(n), Time: O(n^2). For once, those numbers are actually decent.

🧠 Interviewer Brain-Tattoo

“Trying every path is like carrying all your groceries one item at a time—sure, you’ll get there, but your neighbors will talk. Bubble up, be smart, and keep your arms (and code) efficient.”