The O(n) Club: Minimum Falling Path Sum — Because Gravity Isn’t Optional

The O(n) Club: Minimum Falling Path Sum — Because Gravity Isn’t Optional

⚡ TL;DR

Given a grid of integers, start anywhere up top and fall straight down, or diagonally left/right, collecting numbers as you go. Your mission: make that sum as tiny as your patience for off-by-one errors. Brute force melts CPUs—try this instead:

// Brute force idea — only if you like timeouts
int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int min = Integer.MAX_VALUE;
    for (int j = 0; j < n; j++) {
        min = Math.min(min, dfs(matrix, n - 1, j));
    }
    return min;
}
// dfs() here is classic recursion: super clear, but super slow.

🧠 How Devs Usually Mess This Up

If you love stack overflows and mysterious java.lang.ArrayIndexOutOfBoundsException, just ignore the edges of the grid! Others forget they’re allowed to start and finish anywhere on the top or bottom row, not just some fixed column. And for the daredevils: recursion without DP means your function call tree consumes more memory than Chrome after a tab binge. Save yourself—read the instructions and memoize.

🔍 What’s Actually Going On

Think of each cell as a slippery stepping stone on a cliff. You can start on any stone along the top ledge, but every hop downward must land directly below, below-left, or below-right—unless you fancy a mathematical faceplant off the grid. At each cell, you ask: What’s my current misery plus the smallest misery from above? Dynamic programming is just you, refusing to repeat unpleasant trips, remembering the cheapest way down to each and every stone. It’s the algorithmic version of not touching a hot stove twice.

🛠️ PseudoCode

• Initialize your DP: Make a table where dp[i][j] is the minimum sum to get to cell (i, j). Set first row equal to matrix’s first row.
  

  int[][] dp = new int[n][n];
  for (int j = 0; j < n; j++) dp[0][j] = matrix[0][j];

• Fill row by row: For each cell, set:

  dp[i][j] = matrix[i][j] + min(
    dp[i-1][j],
    dp[i-1][j-1] if j > 0,
    dp[i-1][j+1] if j < n-1
  );

  Don’t read off the edge—nobody can afford those hospital bills.
• Boundary checks = sanity checks: When at the extreme left/right, skip the non-existent neighbor.
• Result: The lowest value in the last row of dp (you can end anywhere…)
• Space hack: Only need two rows at a time—your RAM will thank you.

💻 The Code

// O(n^2) DP, optimized space
public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int[] prev = new int[n];
    for (int j = 0; j < n; j++) prev[j] = matrix[0][j];
    for (int i = 1; i < n; i++) {
        int[] curr = new int[n];
        for (int j = 0; j < n; j++) {
            int minPrev = prev[j];
            if (j > 0) minPrev = Math.min(minPrev, prev[j - 1]);
            if (j < n - 1) minPrev = Math.min(minPrev, prev[j + 1]);
            curr[j] = matrix[i][j] + minPrev;
        }
        prev = curr;
    }
    int min = prev[0];
    for (int j = 1; j < n; j++) min = Math.min(min, prev[j]);
    return min;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edges bite: Referencing j - 1 or j + 1 out of bounds? Welcome to the crash zone.
• Don’t start/finish in fixed columns: The fall can (and should) start & finish anywhere—explore all options for maximum interview points (and minimum sums).
• Recursion-lovers: Pure recursion = exponential runtime = tears. Toss in DP or just go bottom-up.

Time: O(n²)
Space: O(n) if you’re cool, O(n²) if you like nostalgia.

🧠 Interviewer Brain-Tattoo

“Dynamic programming: The only falling path where repeating yourself makes you go faster, not crazier.”