[LeetCode] 55. Jump Game

1. Question

You are given an integer array nums. You are initially positioned at the array's 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.

Example 1:

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.

Example 2:

Input: 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.

2. Thoughts

Use Greedy

3. Tips learned

4. My solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_len = nums[0]
        if max_len == 0:
            return True if len(nums) == 1 else False

        for j in range(1, len(nums) - 1):
            max_len -= 1
            max_len = max(max_len, nums[j])

            if max_len == 0:
                return False

        return True

172/172 cases passed (382 ms)
Your runtime beats 77.59 % of python3 submissions
Your memory usage beats 25.95 % of python3 submissions (18.7 MB)

5. AI Solution and Improvements

Your current approach to solving the "Jump Game" problem is quite efficient. It uses a greedy strategy to determine the furthest reachable index at each step. However, I can suggest a few improvements to make the code more concise and possibly easier to understand:

1. Simplify the initial condition check.
2. Utilize a single loop to iterate over the elements.
3. Remove unnecessary checks within the loop.

Here's a revised version of your solution:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reachable = 0
        for i, jump in enumerate(nums):
            if i > max_reachable:
                return False
            max_reachable = max(max_reachable, i + jump)
        return max_reachable >= len(nums) - 1

Explanation:

• max_reachable keeps track of the furthest index that can be reached.
• The loop iterates over each element in nums. If the current index i is greater than max_reachable, it means we've encountered a gap that we cannot jump over, and we return False.
• Otherwise, we update max_reachable with the maximum of its current value and i + jump.
• After the loop, we check if max_reachable is at least the last index of the array (i.e., len(nums) - 1).

This version is more streamlined and eliminates the initial checks by incorporating their logic into the loop. It efficiently handles all cases, including arrays of length 1.