Jump Game II

Medium Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

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. Return the minimum number of jumps to reach nums[n - 1].

Example 1:

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

Optimal Solution

Python

Approach: Greedy BFS Levels

We treat the array as levels. We maintain l and r boundaries of the current jump's reach. For each step, we calculate the farthest we can reach in the next jump (farthest). When i reaches r, we increment jumps and set r = farthest.

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

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

        return res