Solution Explanation: Jump Game

The problem asks whether it's possible to reach the last index of an array, given that each element represents the maximum jump length from that position.

Approach: Greedy Algorithm

The most efficient approach is a greedy algorithm. We iterate through the array, keeping track of the furthest reachable index (mx).

1. Initialization: mx is initialized to 0. This represents the furthest we can reach initially (from index 0).

2. Iteration: We iterate through the array. For each index i:

   • Reachability Check: If mx < i, it means we cannot reach the current index i. Therefore, it's impossible to reach the end, so we return false.
   • Update mx: If we can reach index i, we update mx to the maximum of its current value and i + nums[i]. i + nums[i] represents the furthest index reachable from position i.

3. Result: If we successfully iterate through the entire array without returning false, it means we can reach the last index. We return true.

Time and Space Complexity

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

Code Examples

The following code snippets demonstrate the greedy approach in several programming languages:

Python:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        mx = 0
        for i, x in enumerate(nums):
            if mx < i:
                return False
            mx = max(mx, i + x)
        return True

Java:

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

C++:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int mx = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (mx < i) {
                return false;
            }
            mx = max(mx, i + nums[i]);
        }
        return true;
    }
};

JavaScript:

var canJump = function(nums) {
    let mx = 0;
    for (let i = 0; i < nums.length; i++) {
        if (mx < i) return false;
        mx = Math.max(mx, i + nums[i]);
    }
    return true;
};

These code examples all implement the same greedy algorithm, differing only in syntax. They all achieve a time complexity of O(n) and a space complexity of O(1). The core logic remains consistent across all languages.