55. Jump Game

Problem Statement

link: LeetCode.cn LeetCode

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:

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

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

Solution Approach

The solution involves determining the furthest reachable index while iterating through the list.

Algorithm

1. Initialize Reachability: Start by initializing a variable reach to zero. This variable will keep track of the furthest index we can reach.
2. Iterate Through the List: As we traverse the list, for each index, check if the current index is beyond the reachable index. If yes, it’s impossible to reach the end of the list.
3. Update Reachability: At each step, update the reach value to be the maximum of the current reach and the sum of the current index and its corresponding value (i.e., i + n). This is to account for the maximum jump length from the current position. If at any point, the reachable index is greater than or equal to the last index of the list, we can reach the end.

Implement

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

    
    

Twitter  facebook  Email