45. Jump Game II

Problem Statement

link: https://leetcode.com/problems/jump-game-ii/ https://leetcode.cn/problems/jump-game-ii/

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example:

Input: [2,3,1,1,4] Output: 2

Input: [2,3,0,1,4] Output: 2

Solution Approach

Use a greedy algorithm to keep track of the farthest reachable index through the current jump, and ensure to make a jump once the current index reaches the end of the current jump range.

Algorithm

1. Initialization: Start with jump, curEnd, and curFar initialized to 0. Here, jump keeps track of the number of jumps made, curEnd denotes the end of the current jump range, and curFar tracks the farthest reachable index from the current position.
2. Iterate through nums: For each index i in the array (excluding the last one), update curFar to be the maximum of curFar and i + nums[i], which represents the farthest we can reach from the current position.
3. Make a Jump: If the current index i is equal to curEnd, it means we’ve reached the end of our current jump range and need to make another jump. Increment the jump count and update curEnd to curFar.

Implement

    class Solution: 
      def jump(self, nums: List[int]) -> int:
          jump = curEnd = curFar = 0
          l = len(nums)
          for i in range(l - 1):
              curFar = max(curFar, i + nums[i])
              if curEnd == i:
                  jump += 1
                  curEnd = curFar
          return jump

    
    

Twitter  facebook  Email