readme.md

45. 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 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

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

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

Solution

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        currentEnd = 0
        farthest = 0
        # Traverse from the start to the second to last element,
        # since reaching the last element means we're done
        for i in range(len(nums) - 1):
            # Update the farthest point that can be reached
            farthest = max(farthest, i + nums[i])
            # If we have come to the end of the range we can reach with the current number of jumps
            if i == currentEnd:
                # We need a new jump
                jumps += 1
                # Update the end to the furthest point we can reach
                currentEnd = farthest
                # If at any point the farthest reaches or exceeds the last index, we can stop early
                if currentEnd >= len(nums) - 1:
                    break
        return jumps

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        l = r = 0

        while r < len(num-1):
            farthest = 0
            for i in range(l, r+!):
                farthest = max(farthest, i+nums[i])

            l = r+1
            r= farthest
            res += 1

        return res

Thoughts

Time Complexity

O(n). Although it seems like a nested logic, each element is considered exactly once for updating the farthest and possibly once more for the jump logic, resulting in a linear time complexity.

Neetcodes explanation using color codes is very intuitive.

Space Complexity

O(1). This approach only uses a few variables regardless of the input size.