The O(n) Club: Jump Game III – Exactly, Unforgivingly, To Zero (Or Die Trying)

The O(n) Club: Jump Game III – Exactly, Unforgivingly, To Zero (Or Die Trying)

⚡ TL;DR

You’re stuck in an array where each index is a dramatic crossroads. You can only jump exactly arr[i] steps forward or backward (the flexibility of a brick). Can you land on any index with a zero, without going out of bounds or getting caught in a loopy conspiracy? Here’s the nitty-gritty:

boolean canReach(int[] arr, int start) {
    return dfs(arr, start, new boolean[arr.length]);
}
boolean dfs(int[] arr, int i, boolean[] seen) {
    if (i < 0 || i >= arr.length || seen[i]) return false;
    if (arr[i] == 0) return true;
    seen[i] = true;
    return dfs(arr, i + arr[i], seen) || dfs(arr, i - arr[i], seen);
}

🧠 How Devs Usually Mess This Up

Here’s where things go sideways, courtesy of dev folklore:

• Custom Jumping Gymnastics: Sorry, jumping less than arr[i] is not a thing. No hopscotch, only full launches.
• The “Finish Line” Illusion: This time, you don’t care about the last index—just sniff out a zero anywhere.
• Forgetful Explorer Syndrome: If you don’t mark visited indices, you’ll spiral into the abyss, reliving your mistakes forever. Sound familiar?
• DFS on Mega Arrays: Go recursive on a giant array and Java will bury you in a StackOverflow that your therapist can’t fix.

🔍 What’s Actually Going On

Picture an escape room where each chamber tells you exactly how far to jump. You can leap forward or backward, but only if you love excitement and pain in equal parts. Some rooms are “safe” (), and the rest? Just really tired tiles hoping you move on.

It’s a search party: from your starting cell, explore both directions, but keep a list of places you’ve checked—unless you want a recursion horror story. BFS or DFS does the job, but BFS avoids risking Java’s call stack therapy bills.

🛠️ PseudoCode

• Start Check: If arr[start] is already zero, show off and return true.
• Initialize: Use BFS with a queue (or DFS if you’re feeling spicy, but bring a fire extinguisher for stack overflow).
• Marking Your Territory: Use a boolean array or just graffiti the input with -1 (the problem says you can).
• Exploration:
  • While there are indices left:
    • If arr[i] == 0—bam! You’re done.
    • Otherwise, enqueue i + arr[i] and i - arr[i] if they’re in-bounds and not visited.
• Tough Luck: If nothing pans out, return false and go re-code your life choices.

💻 The Code

// BFS FTW (Forget The Woes)
public boolean canReach(int[] arr, int start) {
    Queue
<integer> queue = new LinkedList<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int i = queue.poll();
        if (i < 0 || i >= arr.length || arr[i] == -1) continue;
        if (arr[i] == 0) return true;
        int jump = arr[i];
        arr[i] = -1; // Visited
        queue.offer(i + jump);
        queue.offer(i - jump);
    }
    return false;
}</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• If start is 0, congrats—speedrun unlocked.
• Multiple zeros? You only need one—don’t collect them like Pokémon.
• Jumps off the board? Just ignore. The array ends for a reason.
• Don’t mark visited? Infinite loops: fun in video games, not in interviews.
• Complexity Check:
  Time: O(n), every index at most once.
  Space: O(n), courtesy of your queue and marking.

🧠 Interviewer Brain-Tattoo

“Jump Game III: Proof that unchecked recursion is just time-traveling to face your own bugs.”