algoadvance

Leetcode 45. Jump Game II

Problem Statement

You are given an array of non-negative integers nums where each element represents the maximum number of steps one can take forward from that position. Your goal is to reach the last index of the array in the minimum number of jumps. You can assume that you can always reach the last index.

Return the minimum number of jumps needed to reach the last index.

Example:

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.

Clarifying Questions

  1. Is there always a non-negative integer in the array? Yes, we are given that there are only non-negative integers in the array.

  2. Will the array always contain at least one element? Yes, the array will contain at least one element.

  3. Can the array contain zeroes? Yes, the array can contain zeroes, but you can assume that there is always a solution that allows reaching the end of the array.

Strategy

To solve this problem, we need to keep track of the furthest position that can be reached with a given number of jumps, updating this as we iterate through the list. We will also need to track:

  1. Current End: The farthest position that can be reached with the current number of jumps.
  2. Furthest: The farthest position that we can reach by making one more jump from any of the indices up to the currentEnd.

We will iterate through the array and, for each index, update the furthest with the farthest we can reach from that index. If we reach the currentEnd, it means that we need another jump to proceed further. Increase the number of jumps and update currentEnd to the furthest.

Code

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;
        
        int jumps = 0;
        int currentEnd = 0;
        int furthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            furthest = Math.max(furthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = furthest;
                if (currentEnd >= n - 1) break;
            }
        }
        
        return jumps;
    }
}

Time Complexity

The time complexity of this approach is O(n) where n is the length of the array nums. We only make a single pass through the array to determine the minimum number of jumps.

Explanation

  1. Initialization: We initialize jumps to 0 for counting the number of jumps, currentEnd to 0 for tracking the range of the current jump, and furthest to 0 for the furthest point we can reach so far.
  2. Traverse the Array: Iterate through the array. For each index, compute the furthest point reachable from that index.
  3. Update Jumps: If the current index reaches currentEnd, it implies that all indices up to currentEnd have been checked, and a new jump is necessary.
  4. Break Condition: If currentEnd becomes greater than or equal to the last index, we can stop further checking as we can reach the end.

This method ensures that we find the minimum number of jumps efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI