Coding

Jump Game VIII

Asked at

ByteDance

Media.net

Salesforce

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where **i < j **if:

nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, or
nums[i] > nums[j] and nums[k] >= nums[i] for all indexes** k **in the range i < k < j.

You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i.

Return the minimum cost to jump to the index n - 1.

Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2] Output: 8 Explanation: You start at index 0.

Jump to index 2 with a cost of costs[2] = 6.
Jump to index 4 with a cost of costs[4] = 2. The total cost is 8. It can be proven that 8 is the minimum cost needed. Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4. These have a total cost of 9 and 12, respectively.

**Input: **nums = [0,1,2], costs = [1,1,1] Output: 2 Explanation: Start at index 0.

Jump to index 1 with a cost of costs[1] = 1.
Jump to index 2 with a cost of costs[2] = 1. The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums[0] <= nums[1].

Input: nums = [5,3,6,7,2], costs = [4,6,5,3,2]

n == nums.length == costs.length
1 <= n <= 105
0 <= nums[i], costs[i] <= 105

cpp

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& costs) {
        // Your code goes here
    }
};

java

class Solution {
    public int minCost(int[] nums, int[] costs) {
        // Your code goes here
    }
}

python

class Solution:
    def minCost(self, nums, costs):
        # Your code goes here

javascript

class Solution {
    minCost(nums, costs) {
        // Your code goes here
    }
}

csharp

class Solution
{
    public long MinCost(int[] nums, int[] costs)
    {
        // Your code goes here
    }
}

func minCost(nums []int, costs []int) int64 {

Stuck? Show a way to structure it+

01Treat indices as graph nodes and dp[i] as the cheapest cost to reach i.
02Use monotonic stacks while scanning to discover valid next-greater-or-equal and next-smaller jump edges.
03Relax dp at the destination of each discovered edge and handle equal values consistently.
04Explain why each monotonic-stack pop yields a legal jump edge exactly once.

Reference answer

A direct check of every pair is O(n squared). The jump rules describe visibility until a blocking value appears, which monotonic stacks can enumerate in linear time. Scan indices left to right with dp[0] = 0 and all other costs infinite. Maintain one decreasing stack for jumps to the next greater-or-equal value and one increasing stack for jumps to the next smaller value. When the current value breaks a stack's monotonic order, pop the exposed indices and relax dp[current] from each popped index plus cost[current]; the remaining top may also define a legal boundary edge and should be relaxed according to the rule. Push the current index into both structures, removing redundant equal-value entries consistently so invalid duplicate edges are not introduced. Each index is pushed and popped a constant number of times, giving O(n) time and O(n) space. The difficult part is deriving and explaining the legal edges, not the DP addition itself.

Then expect these follow-ups

Which legal edges does each monotonic stack represent?
Tests: invariant depth
How would you verify the optimized result against a quadratic reference?
Tests: testing strategy

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question