Jump Game medium

Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1

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

Output: true

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

Example 2

nums = [3,2,1,0,4]

Output: false

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Steps and Explanation

This problem can be solved using a greedy approach. We maintain a variable reachable which represents the furthest index we can reach so far. We iterate through the array. For each index i, if i is within the reachable range (i <= reachable), we update reachable to the maximum of its current value and i + nums[i] (the furthest we can reach from index i).

If after iterating through the entire array, reachable is greater than or equal to the last index, it means we can reach the end, and we return true. Otherwise, we return false.

Code (Java)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return true; // Already at the end or only one element

        int reachable = 0; // Furthest index reachable so far

        for (int i = 0; i < n; i++) {
            if (i > reachable) return false; // Cannot reach current index

            reachable = Math.max(reachable, i + nums[i]); // Update reachable index
            if (reachable >= n - 1) return true; // Reached the end
        }

        return false; // Should not reach here if reachable is updated correctly
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space.

Detailed Walkthrough of Example 1 ([2,3,1,1,4])

1. n = 5, reachable = 0
2. Iteration 1 (i=0): 0 <= 0 (true), reachable = max(0, 0+2) = 2
3. Iteration 2 (i=1): 1 <= 2 (true), reachable = max(2, 1+3) = 4
4. Iteration 3 (i=2): 2 <= 4 (true), reachable = max(4, 2+1) = 4
5. Iteration 4 (i=3): 3 <= 4 (true), reachable = max(4, 3+1) = 4
6. Iteration 5 (i=4): 4 <= 4 (true), reachable = max(4, 4+4) = 8. Since reachable (8) >= n-1 (4), the function returns true.

Detailed Walkthrough of Example 2 ([3,2,1,0,4])

1. n = 5, reachable = 0
2. Iteration 1 (i=0): 0 <= 0 (true), reachable = max(0, 0+3) = 3
3. Iteration 2 (i=1): 1 <= 3 (true), reachable = max(3, 1+2) = 3
4. Iteration 3 (i=2): 2 <= 3 (true), reachable = max(3, 2+1) = 3
5. Iteration 4 (i=3): 3 <= 3 (true), reachable = max(3, 3+0) = 3. Here, we reach index 3, but the maximum jump is 0.
6. The loop continues, but i (4) will be greater than reachable (3), so the function returns false.

This demonstrates how the greedy approach efficiently determines if the end of the array is reachable.