We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Jumps to Reach the Last Index

Number: 2855

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a 0-indexed array of integers and an integer target, start at index 0 and try to reach index n - 1. In one jump from index i to index j (with i < j), you can only jump if the difference between nums[j] and nums[i] is between -target and target (inclusive on both ends). Return the maximum number of jumps that can be made to reach index n - 1. If it is not possible to reach the last index, return -1.

Key Insights

  • This is essentially a longest path problem on a Directed Acyclic Graph (DAG) because you can only jump forward.
  • Use dynamic programming where dp[i] represents the maximum number of jumps required to reach index i.
  • Start with dp[0] initialized to 0 and use the condition -target <= nums[j] - nums[i] <= target to update the dp value for j from i.
  • The answer will be dp[n-1] if it was updated; otherwise, return -1 if the last index is unreachable.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the array. Space Complexity: O(n) for the dp array.

Solution

We solve the problem using a dynamic programming approach by iterating through the array and, for each index, checking all subsequent indices we can jump to while satisfying the given difference condition. For each valid jump from index i to j, we update dp[j] as the maximum of its current value and dp[i] + 1. Finally, if the last index has been reached, we return the dp value, otherwise we return -1.

Code Solutions

# Python solution for Maximum Number of Jumps to Reach the Last Index
def maximumJumps(nums, target):
    n = len(nums)
    # Initialize dp array with -infinity to represent unreachable indices;
    # dp[0] is set to 0 as we start at index 0.
    dp = [-float('inf')] * n
    dp[0] = 0

    # For every index 'i', try to jump to every index 'j' > i
    for i in range(n):
        # Only consider reachable indices
        if dp[i] == -float('inf'):
            continue
        # Check for all possible jumps from index i
        for j in range(i + 1, n):
            # Check if the jump from i to j is allowed
            if -target <= nums[j] - nums[i] <= target:
                dp[j] = max(dp[j], dp[i] + 1)
    
    # If the last index is still unreachable, return -1.
    return dp[-1] if dp[-1] != -float('inf') else -1

# Example usage:
print(maximumJumps([1,3,6,4,1,2], 2))  # Expected output: 3
print(maximumJumps([1,3,6,4,1,2], 3))  # Expected output: 5
print(maximumJumps([1,3,6,4,1,2], 0))  # Expected output: -1
← Back to All Questions