View on NeetCode
View on LeetCode

Problem

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

Approach 1: Greedy (BFS-like)

The key insight is to treat this as a BFS problem where each “level” is all positions reachable with the same number of jumps.

Implementation

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0

        jumps = 0
        current_end = 0  # End of current jump range
        farthest = 0     # Farthest position reachable

        for i in range(len(nums) - 1):
            # Update farthest position we can reach
            farthest = max(farthest, i + nums[i])

            # If we've reached the end of current jump range
            if i == current_end:
                jumps += 1
                current_end = farthest

                # Early exit if we can reach the end
                if current_end >= len(nums) - 1:
                    break

        return jumps

Approach 2: Greedy (Simpler)

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = 0
        current_max = 0
        next_max = 0

        for i in range(n - 1):
            next_max = max(next_max, i + nums[i])

            if i == current_max:
                jumps += 1
                current_max = next_max

        return jumps

Approach 3: Dynamic Programming

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        dp[0] = 0

        for i in range(n):
            for j in range(1, nums[i] + 1):
                if i + j < n:
                    dp[i + j] = min(dp[i + j], dp[i] + 1)

        return dp[n - 1]

Complexity Analysis

Greedy Approaches:

• Time Complexity: O(n), single pass through array.
• Space Complexity: O(1), constant extra space.

DP Approach:

• Time Complexity: O(n * k), where k is average jump length.
• Space Complexity: O(n) for dp array.

Key Insights

1. BFS Intuition: Think of it as BFS where each level represents positions reachable with the same number of jumps.

2. Current Range: Track the end of the current jump’s range. When we reach it, we must make another jump.

3. Farthest Tracking: While exploring the current range, track the farthest position we can reach for the next jump.

4. Greedy Choice: Always jump to the position that maximizes our reach for the next jump.

5. Guaranteed Solution: Since we’re guaranteed to reach the end, we don’t need to check if jumps is possible.

6. Lazy Jump: We don’t decide where to jump until we must (when reaching end of current range).