The O(n) Club: Jump Game — Greedy or Bust

The O(n) Club: Jump Game — Greedy or Bust

⚡ TL;DR

Here’s the deal: stand at the start of an array, each number = maximum jump forward. Can you hop to the last index without falling flat? Brute force is about as efficient as debugging without Stack Overflow. Use greedy: always record the furthest you can jump. If you pass the end, high five. If you can’t reach a spot, it’s game over.

// Brute-force: the slow, sad way
boolean canJump(int[] nums) {
    return canJumpFrom(0, nums);
}
boolean canJumpFrom(int pos, int[] nums) {
    if (pos >= nums.length - 1) return true;
    int furthest = Math.min(pos + nums[pos], nums.length - 1);
    for (int next = pos + 1; next <= furthest; next++) {
        if (canJumpFrom(next, nums)) return true;
    }
    return false;
}

🧠 How Devs Usually Mess This Up

Most folks see “jump” and immediately code up some heroic DFS, sprinkle recursive fairy dust, then quietly cry when their solution times out. Here’s a tip: don’t invent a rocket to jump a puddle. No need for DP, backtracking, or prayer circles. And seriously, stop confusing Jump Game with Jump Game II—speed isn’t the point, just the finish line.

🔍 What’s Actually Going On

This is a side-scrolling video game—each tile tells you its launch power. All that matters: “From where I am, how far could I possibly go?” As you march right, update your max reach. If you step past your reach, you land in a pit—Mario music of doom plays. But if your max reach ever meets or beats the last index, congrats: you’ve beaten the system with greed (the good kind).

🛠️ PseudoCode

• maxReach = 0 — Your current world record for longest jump.
• For each index i from 0 to nums.length – 1:
  • If i > maxReach: can’t reach this platform. Game over.
  • Else, update maxReach = max(maxReach, i + nums[i]).
  • If maxReach >= nums.length - 1: You made it! Return true.
• Finished loop? If never returned true, return false. Rerun after more coffee.

💻 The Code

// Greedy all the way — fast and interview-approved
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false; // Plummeted into the digital abyss
        }
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) {
            return true; // Raise the victory flag
        }
    }
    return true; // Survived the whole ride
}

⚠️ Pitfalls, Traps & Runtime Smacks

• 1-element array? Already at the finish. Take a break.
• No back-jumping: Negative jumps don’t exist. Only forward, only up.
• Zeros: Land on a zero before the end? That’s a trap block—RIP.
• Performance: O(n) time, O(1) space—runs faster than your last coffee-fueled refactor.

🧠 Interviewer Brain-Tattoo

“Greedy isn’t always bad. If you’re thinking recursion here, your code’s already faceplanted. Stay greedy.”