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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Jump Game VIII

Number: 2056

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

You are given a 0-indexed integer array nums and a cost array costs. Starting at index 0, you can jump from index i to j (with i < j) if one of the following conditions holds:

  • nums[i] <= nums[j] and every element between i and j is strictly less than nums[i], or
  • nums[i] > nums[j] and every element between i and j is greater than or equal to nums[i].

The cost of jumping to index j is given by costs[j]. Your task is to compute the minimum total cost required to reach index n - 1.

Key Insights

  • The problem can be seen as finding the shortest path in a directed acyclic graph (DAG) where nodes are indices.
  • A dynamic programming (DP) solution is applicable where dp[i] represents the minimum cost to reach index i.
  • Two monotonic stacks are used to efficiently process valid jumps based on the two conditions (increasing and decreasing jumps).
  • The increasing stack handles jumps where nums[i] <= nums[j] by ensuring the intermediate elements are less than nums[i].
  • The decreasing stack handles jumps where nums[i] > nums[j] by ensuring the intermediate elements are greater than or equal to nums[i].

Space and Time Complexity

Time Complexity: O(n), as each index is processed with amortized constant time stack operations.
Space Complexity: O(n), used by the dp array and the two stacks.

Solution

We solve the problem using a DP approach where dp[i] holds the minimum cost to reach index i. We iterate through the array while maintaining two monotonic stacks:

  1. For indices where nums[i] should be less than or equal to nums[j], we pop from the increasing stack until nums[stack.top()] <= nums[i]. Then, we update dp[i] using the top of this stack.
  2. Similarly, for the second condition, we maintain a decreasing stack by popping until nums[stack.top()] >= nums[i] and then update dp[i]. Finally, the answer is given by dp[n - 1].

Code Solutions

# Function to compute the minimum jump cost.
def min_jump_cost(nums, costs):
    n = len(nums)
    dp = [float('inf')] * n  # dp[i] stores the minimum cost to reach index i.
    dp[0] = 0  # Starting point cost is 0.
    
    # Initialize two stacks for increasing and decreasing conditions.
    inc_stack = []  # For handling jumps where nums[i] <= nums[j]
    dec_stack = []  # For handling jumps where nums[i] > nums[j]
    
    inc_stack.append(0)
    dec_stack.append(0)
    
    # Process each index from 1 to n-1.
    for i in range(1, n):
        # Process the increasing stack.
        while inc_stack and nums[inc_stack[-1]] > nums[i]:
            inc_stack.pop()
        if inc_stack:
            dp[i] = min(dp[i], dp[inc_stack[-1]] + costs[i])
        inc_stack.append(i)
        
        # Process the decreasing stack.
        while dec_stack and nums[dec_stack[-1]] < nums[i]:
            dec_stack.pop()
        if dec_stack:
            dp[i] = min(dp[i], dp[dec_stack[-1]] + costs[i])
        dec_stack.append(i)
    
    return dp[n - 1]

# Example usages:
nums1 = [3,2,4,4,1]
costs1 = [3,7,6,4,2]
print(min_jump_cost(nums1, costs1))  # Expected output: 8

nums2 = [0,1,2]
costs2 = [1,1,1]
print(min_jump_cost(nums2, costs2))  # Expected output: 2
← Back to All Questions