Jump Game II medium

Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

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 from index 0 to 1, then 3 from index 1 to 4.

Example 2

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

Steps

1. Initialization:

   • jumps (integer): Keeps track of the minimum number of jumps needed. Initialized to 0.
   • currentReach (integer): Represents the farthest index reachable from the current jump. Initialized to 0.
   • maxReach (integer): Represents the farthest index reachable in the next jump. Initialized to 0.

2. Iteration:

   • Iterate through the nums array using a for loop with index i.
   • For each index i, update maxReach to be the maximum of maxReach and i + nums[i]. This calculates the furthest index reachable from the current position i.
   • If i reaches currentReach, it means we've reached the limit of our current jump. Increment jumps and update currentReach to maxReach. This signifies a new jump.
   • If maxReach reaches or exceeds the last index of nums, the loop terminates because we've found a valid path.

3. Return:

   • Return the value of jumps.

Explanation

The algorithm uses a greedy approach. At each step, it determines the maximum reachable index from the current position. Once the current jump's reach is exhausted, it signifies the need for another jump. The maxReach variable keeps track of the furthest point we can reach at any given time. This ensures that we're always making the largest jump possible at each stage, minimizing the overall number of jumps.

Code

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0  # Already at the end or only one element

    jumps = 0
    currentReach = 0
    maxReach = 0

    for i in range(n - 1):  # Iterate until second to last element
        maxReach = max(maxReach, i + nums[i])
        if i == currentReach:  # Current jump exhausted
            jumps += 1
            currentReach = maxReach
            if currentReach >= n - 1:
                break  # Reached the end

    return jumps

Complexity

• Time Complexity: O(N), where N is the length of the nums array. We iterate through the array once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.