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

Hiring now

Salesforce has 1,420 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineering MTS
India - Hyderabad
Senior Software Engineer, Data Ingestion
Georgia - Atlanta
Software Engineering AMTS (College Grad)
California - San Francisco

Or practice this question first

Next question