algoadvance

Leetcode 45. Jump Game II

Problem Statement

You are given a 0-indexed array of integers nums of length n. Initially, you are positioned at the first index of the array.

Each element nums[i] represents the maximum length of a forward jump from index i.

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: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

Clarifying Questions

  1. Constraints: How large can the array be?
    • 1 <= nums.length <= 10^4
    • 0 <= nums[i] <= 1000
  2. Edge cases: Should I consider arrays of length 1?
    • Yes, but in such cases, the result is trivially 0 since you’re already at the last index.

Strategy

To solve this problem, we will use a greedy approach:

  1. Track the farthest index we can reach from the current index.
  2. Maintain a count of the number of jumps used.
  3. Keep a currentEnd variable to represent the end of the range for the current jump.
  4. Iterate through the array and, for each index, update the farthest index that can be reached.
  5. If we reach the currentEnd, increment the jump count and update currentEnd to farthest.

Code

Here is the C++ implementation:

#include <vector>
#include <iostream>
#include <algorithm>

int jump(std::vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;
    
    int jumps = 0, currentEnd = 0, farthest = 0;
    
    for (int i = 0; i < n - 1; ++i) {
        farthest = std::max(farthest, i + nums[i]);
        
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
            
            if (currentEnd >= n - 1) {
                break;
            }
        }
    }
    
    return jumps;
}

// Example usage
int main() {
    std::vector<int> nums = {2, 3, 1, 1, 4};
    std::cout << "Minimum number of jumps: " << jump(nums) << std::endl; // Output: 2
    return 0;
}

Time Complexity

This implementation ensures that we find the minimum number of jumps required to reach the last index in an efficient manner.

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