Jump Game

Jump Game looks like a maze puzzle. You stand at the start. Each spot tells you how far you can jump. The question is simple to ask but tricky to answer fast. Can you reach the last spot at all? The slow way checks every possible path. The fast way only tracks one number. That gap is what the interviewer wants to see.

🎯 The Problem

You get an array of numbers and must find out if you can reach the last position.

• Each number is the most steps you can jump forward from that position.
• You start at position 0.
• The goal is the last index.
• Return true if some set of jumps lands you there.
• Return false if you get stuck before the end.

Let us say the array is [2, 3, 1, 1, 4]. From position 0 the value is 2. So you can jump 1 or 2 steps forward.

Input:  nums = [2, 3, 1, 1, 4]
Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Now look at a case where you cannot make it. The zero is the trap. If you land on a 0 and it is not the last spot, you cannot move.

Input:  nums = [3, 2, 1, 0, 4]
Output: false

Explanation: You always reach index 3 with value 0, so you stop before the end.

Here is a picture of the second case. Each box shows how far you can jump from there. The 0 box has no arrow out.

🐢 Approach 1: Recursion (Brute Force)

Try every possible jump from every spot.

The idea:

• A recursion is a function that calls itself on a smaller piece of the same problem.
• From position 0, try jumping 1 step, then 2, up to the value there.
• From each new spot, try every jump again.
• If any chain of jumps reaches the end, the answer is true.

Why it is weak:

• You visit the same spots again and again through different paths.
• The branches keep splitting, so the time is about O(2^n).
• On a big array this becomes painfully slow.

Here is the plain recursion code:

def can_jump(nums):
    def dfs(index):
        if index >= len(nums) - 1:
            return True
        return any(dfs(index + step) for step in range(1, nums[index] + 1))

    return dfs(0)

⚡ Approach 2: Recursion With Memory (Better)

The idea in one line: store each spot’s answer the first time you compute it, then reuse it.

The idea:

• This is dynamic programming, which is recursion plus a memory of past answers.
• Each spot has a fixed answer: can you reach the end from here, yes or no.
• Compute it once, save it, never recompute it.

Why it is better:

• No spot is solved twice. So the repeated work is gone.
• Time drops to O(n²). For each spot you still scan the spots it can reach.

Why it is still not best:

• It uses O(n) extra space for the memory.
• It still does O(n²) work. We can do the whole thing in one pass.

Here is the memoized recursion code:

from functools import lru_cache


def can_jump(nums):
    @lru_cache(None)
    def dfs(index):
        if index >= len(nums) - 1:
            return True
        return any(dfs(index + step) for step in range(1, nums[index] + 1))

    return dfs(0)

🚀 Approach 3: Greedy Farthest Reach (Best)

The idea in one line: track only the farthest index you can reach so far.

The idea:

• Keep one number, the farthest index reachable.
• To reach the end, all that matters is whether your reach ever covers the last index.
• You never need the exact path, only how far forward you can stretch.

How it works:

• Walk the array from left to right.
• If the current index is past your reach, you can never stand here. Return false.
• Otherwise update reach to the bigger of the old reach and i + nums[i].
• If the loop finishes without getting stuck, return true.

Why it is fast:

• One pass through the array. So it is O(n).
• Just one variable, so O(1) extra space.
• Greedy means you keep the single best reach and trust it.

Here is a dry run of the greedy reach on [2, 3, 1, 1, 4]. Watch the reach grow until it covers the last index.

Steps to Solve

1. Start with reach = 0. This is the farthest index you can get to.
2. Walk through the array with the index i from start to end.
3. If i is greater than reach, you cannot stand here. Return false.
4. Update reach to the bigger of reach and i + nums[i].
5. If reach already covers the last index, you can stop early and return true.
6. If the loop finishes without getting stuck, return true.

#include <stdio.h>
#include <stdbool.h>

bool canJump(int nums[], int n) {
    int reach = 0;  // farthest index we can get to
    for (int i = 0; i < n; i++) {
        if (i > reach) {       // we cannot even stand here
            return false;
        }
        int far = i + nums[i];     // farthest from this spot
        if (far > reach) {
            reach = far;           // remember the best reach
        }
    }
    return true;
}

int main(void) {
    int nums[] = {2, 3, 1, 1, 4};
    int n = 5;
    printf("%s\n", canJump(nums, n) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canJump(vector<int>& nums) {
    int reach = 0;  // farthest index we can get to
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) {        // cannot stand here
            return false;
        }
        reach = max(reach, i + nums[i]);  // best reach so far
    }
    return true;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << (canJump(nums) ? "true" : "false") << endl;
    return 0;
}

true

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int reach = 0;  // farthest index we can get to
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) {        // cannot stand here
                return false;
            }
            reach = Math.max(reach, i + nums[i]);  // best reach so far
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums = { 2, 3, 1, 1, 4 };
        System.out.println(canJump(nums));
    }
}

true

def can_jump(nums):
    reach = 0  # farthest index we can get to
    for i, step in enumerate(nums):
        if i > reach:              # cannot stand here
            return False
        reach = max(reach, i + step)  # best reach so far
    return True


nums = [2, 3, 1, 1, 4]
print(can_jump(nums))

True

function canJump(nums) {
  let reach = 0; // farthest index we can get to
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) {        // cannot stand here
      return false;
    }
    reach = Math.max(reach, i + nums[i]); // best reach so far
  }
  return true;
}

const nums = [2, 3, 1, 1, 4];
console.log(canJump(nums));

true

Let us walk through the Python version line by line, because the greedy idea lives in just a few lines.

reach = 0 sets up the one number we care about. It is the farthest index we can currently get to. At the start we have only reached position 0.

for i, step in enumerate(nums): walks the array. Here i is the position and step is how far we can jump from it. We need both, so enumerate gives them together.

if i > reach: return False is the trap check. If the current position is beyond our farthest reach, we never could have arrived here. So the end is impossible and we stop.

reach = max(reach, i + step) is the heart of the greedy move. From this spot we can stretch to i + step. We keep whichever is larger, the old reach or this new one. We never need the path, only the best reach.

return True runs if we finished the loop without ever getting stuck. That means our reach always covered the next spot, so the end is reachable.

⏱️ Time and Space Complexity

The recursion tries every path, so it is very slow and can repeat work. Adding memory turns it into dynamic programming, which is faster but still scans pairs of spots. The greedy way only keeps one number and one loop. So it trades nothing and still wins. That takes the time all the way down to O(n) with O(1) extra space.

🧩 Key Takeaways

• ✅ You only need one number, the farthest index you can reach so far.
• ✅ If the current position is past your reach, you are stuck and the answer is false.
• ✅ At each spot, update the reach to the bigger of the old reach and i + nums[i].
• ✅ Greedy works here because only the best reach matters, not the exact path.
• ✅ This runs in O(n) time with O(1) extra space, much better than recursion.

🚀 What’s Next?

• Jump Game II
• Gas Station