Jump Game

Problem Link

Leetcode - Jump Game

Problem Statement

You are given an integer array nums. You are initially positioned at the first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Intuition

At every index i, we can jump from 1 to nums[i] steps forward. We need to check whether there's any path from index 0 to n-1 by making valid jumps.

Choice Diagram

At index i:
      /--> Try i + 1
i -> i+1, i+2, ..., i + nums[i]
      \--> Try i + nums[i]

1. Recursion (IBH Format)

IBH Method

• I: Index i (current position)

• B: If i >= n-1, return true.

• H: Loop through all jumps from 1 to nums[i] and try each recursively.

public class Solution {
    public boolean canJumpFrom(int i, int[] nums) {
        if (i >= nums.length - 1) return true;

        for (int j = 1; j <= nums[i]; j++) {
            if (canJumpFrom(i + j, nums)) {
                return true;
            }
        }
        return false;
    }

    public boolean canJump(int[] nums) {
        return canJumpFrom(0, nums);
    }
}

Time Complexity: Exponential

Space Complexity: O(n) (stack space)

2. Memoization (Top-Down DP)

import java.util.Arrays;

public class Solution {
    public boolean canJumpFrom(int i, int[] nums, int[] dp) {
        if (i >= nums.length - 1) return true;
        if (dp[i] != -1) return dp[i] == 1;

        for (int j = 1; j <= nums[i]; j++) {
            if (canJumpFrom(i + j, nums, dp)) {
                dp[i] = 1;
                return true;
            }
        }

        dp[i] = 0;
        return false;
    }

    public boolean canJump(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        return canJumpFrom(0, nums, dp);
    }
}

Time Complexity: O(n²)

Space Complexity: O(n) (stack) + O(n) (dp array)

3. Tabulation (Bottom-Up DP)

We iterate from the end and determine if we can reach the last index from each position.

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[n - 1] = true;

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                if (dp[i + j]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[0];
    }
}

Time Complexity: O(n²)

Space Complexity: O(n)

4. Space Optimized (Greedy)

Since we only care about the farthest index reachable, we can track it greedily.

public class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) return false;
            farthest = Math.max(farthest, i + nums[i]);
        }
        return true;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Dry Run

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

• i = 0: Can jump to 1 or 2

• i = 1: Can jump to 2, 3, or 4 → reached

Output: true

Conclusion