The O(n) Club: Minimum Path Sum: Grid Torture for People Who Hate Left Turns

The O(n) Club: Minimum Path Sum – Grid Torture for People Who Hate Left Turns

⚡ TL;DR

Start top-left, zigzag to bottom-right, counting up the cheapest cell numbers. Only go right or down—like a robot programmed by someone with navigation anxiety. Brute force? You’ll age before you finish. Java DP, or bust:

// Classic recursive nope-zone
int minPathSum(int[][] grid, int i, int j) {
    if (i == 0 && j == 0) return grid[0][0];
    if (i < 0 || j < 0) return Integer.MAX_VALUE;
    return grid[i][j] + Math.min(
        minPathSum(grid, i-1, j),
        minPathSum(grid, i, j-1)
    );
}

🧠 How Devs Usually Mess This Up

Ah, classic rookie grid-move disasters:

• Freedom of Movement, you wish: Attempting to move left, up, or diagonally, like you’re auditioning for Pac-Man. No dice—right or down only! Gravity and traffic laws strictly enforced.
• Recursion-forever pain: Awesome, you used recursion! But no memoization or DP? Say hello to exponential tragedy and a CPU meltdown.
• Copy-pasting wrong grid logic: Minimum Falling Path Sum lets you diagonally drop like a confused raindrop. This is NOT that. Read. The. Question.

🔍 What’s Actually Going On

Imagine a warehouse robot. It’s not allowed to reverse or moonwalk—it can only scoot right and down. At any spot, it has to decide: should I come from above or from the left? Always take whichever hurts your travel budget less. That sum, plus the current “cell tax,” gets stashed in the grid. By the time you lurch into the bottom-right corner, you’ve got the lightest possible bill.

Picture it: path planning for robots with stage fright. Or seam carving through an image (same logic). Each step just builds on the cheapest way in.

🛠️ PseudoCode

• Step 1: Loop over grid rows, then columns—handle top-left (0,0) as a special snowflake.
• Step 2: For row 0 (first row), can only come from the left:

  grid[0][j] += grid[0][j-1];

• Step 3: For column 0 (first column), can only come from above:

  grid[i][0] += grid[i-1][0];

• Step 4: The rest:

  grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);

  —minimum cost from top or left neighbor.
• Step 5: Who’s the boss? grid[m-1][n-1] is your final answer. It’s that easy. (Narrator: It was not that easy.)

💻 The Code

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            else if (i == 0) grid[i][j] += grid[i][j - 1];
            else if (j == 0) grid[i][j] += grid[i - 1][j];
            else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[m-1][n-1];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Grid[-1][*] Faceplant: Sneaking off the grid means Java exceptions and sadness. Boundaries are real.
• In-place DP Side-Effects: You’re allowed to overwrite the grid—unless you ever need it pristine again. Need the original? Use a clone, pay up in RAM.
• Runtime Reality: Each cell gets touched, O(mn) time. Mutating means O(1) space—fancy, but don’t brag, your interviewer’s seen it before.
• Wrong Algorithm, Wrong Problem: Copying logic from falling path, triangle, or knight-move problems? Get ready for an expected “time limit exceeded.”

🧠 Interviewer Brain-Tattoo

“If you’re tempted to move left, that’s not a coding bug—it’s a reading bug. Grid DP: The real minimum is in the reading, not the sum.”