Practice/Amazon/Leetcode 45. Jump Game II

Leetcode 45. Jump Game II

CodingOptional

Problem

You are given an array of non-negative integers where each element represents your maximum jump length from that position. Starting at the first index, determine the minimum number of jumps required to reach the last index of the array.

You can assume that you can always reach the last index from the starting position.

Requirements

1. Return the minimum number of jumps needed to reach the last index
2. Each element in the array indicates the maximum distance you can jump forward from that position
3. You must find the optimal strategy that minimizes the total number of jumps
4. The solution should handle arrays of varying sizes efficiently

Constraints

• 1 ≤ nums.length ≤ 10,000
• 0 ≤ nums[i] ≤ 1,000
• It is guaranteed that you can reach the last index
• Time complexity should be O(n) or better
• Space complexity should be O(1) if possible

Examples

Example 1:

Input: nums = [2, 3, 1, 1, 4] Output: 2 Explanation: The optimal strategy is to jump from index 0 to index 1 (1 step forward), then from index 1 to index 4 (3 steps forward). This takes 2 jumps total.

Example 2:

Input: nums = [5, 1, 1, 1, 1] Output: 1 Explanation: Since the first element allows a jump of up to 5 positions, we can reach the last index in just one jump.

Example 3:

Input: nums = [1, 1, 1, 1] Output: 3 Explanation: We must jump one position at a time: index 0 → 1 → 2 → 3, requiring 3 jumps.