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

Jump Game V

Number: 1466

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of integers and an integer d, you can jump from any index i to any index j (either left or right within a distance d) if and only if arr[i] > arr[j] and every index between i and j has a value strictly lower than arr[i]. The goal is to determine the maximum number of indices you can visit starting from any index.

Key Insights

  • Use Depth-First Search (DFS) with memoization (Dynamic Programming) to avoid recalculating subproblems.
  • At each index, try to explore jumps in both left and right directions.
  • Stop exploring further in a direction when you hit an element that is not lower than the current element, since the jump condition would break.
  • The answer is the maximum number of indices that can be visited starting from any index.

Space and Time Complexity

Time Complexity: O(n*d) in the worst case, where n is the number of elements and d is the maximum jump distance. Space Complexity: O(n) due to the memoization array and recursion stack.

Solution

We solve this problem using a DFS approach enhanced with memoization. For every index, we calculate the maximum jumps possible starting from that index. We iterate for up to d steps in both the left and right directions, ensuring at each step that the next position has a lower value than the current one and that no intermediate value violates this condition. The result for each index is stored so that it doesn't need to be computed again. Finally, the maximum value among all indices is returned as the result.

Code Solutions

def maxJumps(arr, d):
    n = len(arr)
    # dp[i] stores the maximum number of indices visited starting at index i
    dp = [-1] * n

    def dfs(i):
        # if already computed, return stored result
        if dp[i] != -1:
            return dp[i]
        
        # At least we can always visit the current index
        best = 1
        
        # Explore right direction
        for j in range(i + 1, min(n, i + d + 1)):
            # if the jump is valid (next index has a lower value)
            if arr[j] < arr[i]:
                best = max(best, 1 + dfs(j))
            else:
                # further jumps in this direction are blocked
                break
        
        # Explore left direction
        for j in range(i - 1, max(-1, i - d - 1), -1):
            # if the jump is valid
            if arr[j] < arr[i]:
                best = max(best, 1 + dfs(j))
            else:
                # further jumps in this direction are blocked
                break
        
        dp[i] = best
        return dp[i]
    
    # Compute the best result for each index and return the maximum value
    return max(dfs(i) for i in range(n))


# Example usage:
# print(maxJumps([6,4,14,6,8,13,9,7,10,6,12], 2))
← Back to All Questions