Jump Game VIII

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 _theminimum cost to jump to the index _n - 1.

Examples

Example 1:

1
2
3
4
5
6
7
8


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.

Example 2:

1
2
3
4
5
6


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].

Constraints:

n == nums.length == costs.length
1 <= n <= 10^5
0 <= nums[i], costs[i] <= 10^5

Solution

Method 1 – Monotonic Stack + Dijkstra’s Algorithm

Intuition

We need to find the minimum cost to reach the last index, where jumps are only allowed to the next greater or next smaller element, skipping all elements in between. This is similar to building a graph where each node connects to its next greater and next smaller nodes, and then finding the shortest path using Dijkstra’s algorithm.

Approach

For each index, use a monotonic stack to precompute the next greater and next smaller indices to the right.
Build a graph where each node has edges to its next greater and next smaller nodes.
Use Dijkstra’s algorithm (priority queue) to find the minimum cost path from index 0 to n-1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    int minCost(vector<int>& nums, vector<int>& costs) {
        int n = nums.size();
        vector<int> nxt_g(n, -1), nxt_s(n, -1);
        vector<int> st;
        // Next greater
        for (int i = n-1; i >= 0; --i) {
            while (!st.empty() && nums[st.back()] <= nums[i]) st.pop_back();
            if (!st.empty()) nxt_g[i] = st.back();
            st.push_back(i);
        }
        st.clear();
        // Next smaller
        for (int i = n-1; i >= 0; --i) {
            while (!st.empty() && nums[st.back()] >= nums[i]) st.pop_back();
            if (!st.empty()) nxt_s[i] = st.back();
            st.push_back(i);
        }
        vector<long long> dist(n, 1e18);
        dist[0] = costs[0];
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.emplace(dist[0], 0);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (int v : {nxt_g[u], nxt_s[u]}) {
                if (v != -1 && dist[v] > d + costs[v]) {
                    dist[v] = d + costs[v];
                    pq.emplace(dist[v], v);
                }
            }
        }
        return dist[n-1] == 1e18 ? -1 : (int)dist[n-1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


func minCost(nums, costs []int) int {
    n := len(nums)
    nxtG := make([]int, n)
    nxtS := make([]int, n)
    for i := range nxtG { nxtG[i], nxtS[i] = -1, -1 }
    st := []int{}
    for i := n-1; i >= 0; i-- {
        for len(st) > 0 && nums[st[len(st)-1]] <= nums[i] { st = st[:len(st)-1] }
        if len(st) > 0 { nxtG[i] = st[len(st)-1] }
        st = append(st, i)
    }
    st = []int{}
    for i := n-1; i >= 0; i-- {
        for len(st) > 0 && nums[st[len(st)-1]] >= nums[i] { st = st[:len(st)-1] }
        if len(st) > 0 { nxtS[i] = st[len(st)-1] }
        st = append(st, i)
    }
    dist := make([]int64, n)
    for i := range dist { dist[i] = 1<<60 }
    dist[0] = int64(costs[0])
    pq := &heapq{}
    heap.Init(pq)
    heap.Push(pq, [2]int64{dist[0], 0})
    for pq.Len() > 0 {
        x := heap.Pop(pq).([2]int64)
        d, u := x[0], int(x[1])
        if d > dist[u] { continue }
        for _, v := range []int{nxtG[u], nxtS[u]} {
            if v != -1 && dist[v] > d+int64(costs[v]) {
                dist[v] = d + int64(costs[v])
                heap.Push(pq, [2]int64{dist[v], int64(v)})
            }
        }
    }
    if dist[n-1] == 1<<60 { return -1 }
    return int(dist[n-1])
}
// heapq implements heap.Interface for [][2]int64 (min-heap by first element)
type heapq [][2]int64
func (h heapq) Len() int           { return len(h) }
func (h heapq) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h heapq) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *heapq) Push(x any)        { *h = append(*h, x.([2]int64)) }
func (h *heapq) Pop() any          { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


import java.util.*;
class Solution {
    public int minCost(int[] nums, int[] costs) {
        int n = nums.length;
        int[] nxtG = new int[n], nxtS = new int[n];
        Arrays.fill(nxtG, -1); Arrays.fill(nxtS, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n-1; i >= 0; --i) {
            while (!st.isEmpty() && nums[st.peek()] <= nums[i]) st.pop();
            if (!st.isEmpty()) nxtG[i] = st.peek();
            st.push(i);
        }
        st.clear();
        for (int i = n-1; i >= 0; --i) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            if (!st.isEmpty()) nxtS[i] = st.peek();
            st.push(i);
        }
        long[] dist = new long[n];
        Arrays.fill(dist, (long)1e18);
        dist[0] = costs[0];
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{dist[0], 0});
        while (!pq.isEmpty()) {
            long[] x = pq.poll();
            long d = x[0]; int u = (int)x[1];
            if (d > dist[u]) continue;
            for (int v : new int[]{nxtG[u], nxtS[u]}) {
                if (v != -1 && dist[v] > d + costs[v]) {
                    dist[v] = d + costs[v];
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist[n-1] == (long)1e18 ? -1 : (int)dist[n-1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


import java.util.*
class Solution {
    fun minCost(nums: IntArray, costs: IntArray): Int {
        val n = nums.size
        val nxtG = IntArray(n) { -1 }
        val nxtS = IntArray(n) { -1 }
        val st = ArrayDeque<Int>()
        for (i in n-1 downTo 0) {
            while (st.isNotEmpty() && nums[st.last()] <= nums[i]) st.removeLast()
            if (st.isNotEmpty()) nxtG[i] = st.last()
            st.addLast(i)
        }
        st.clear()
        for (i in n-1 downTo 0) {
            while (st.isNotEmpty() && nums[st.last()] >= nums[i]) st.removeLast()
            if (st.isNotEmpty()) nxtS[i] = st.last()
            st.addLast(i)
        }
        val dist = LongArray(n) { 1e18.toLong() }
        dist[0] = costs[0].toLong()
        val pq = PriorityQueue(compareBy<Pair<Long, Int>> { it.first })
        pq.add(dist[0] to 0)
        while (pq.isNotEmpty()) {
            val (d, u) = pq.poll()
            if (d > dist[u]) continue
            for (v in listOf(nxtG[u], nxtS[u])) {
                if (v != -1 && dist[v] > d + costs[v]) {
                    dist[v] = d + costs[v]
                    pq.add(dist[v] to v)
                }
            }
        }
        return if (dist[n-1] == 1e18.toLong()) -1 else dist[n-1].toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


def min_cost(nums: list[int], costs: list[int]) -> int:
    n = len(nums)
    nxt_g = [-1]*n
    nxt_s = [-1]*n
    st = []
    for i in range(n-1, -1, -1):
        while st and nums[st[-1]] <= nums[i]: st.pop()
        if st: nxt_g[i] = st[-1]
        st.append(i)
    st.clear()
    for i in range(n-1, -1, -1):
        while st and nums[st[-1]] >= nums[i]: st.pop()
        if st: nxt_s[i] = st[-1]
        st.append(i)
    import heapq
    dist = [float('inf')]*n
    dist[0] = costs[0]
    pq = [(dist[0], 0)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v in (nxt_g[u], nxt_s[u]):
            if v != -1 and dist[v] > d + costs[v]:
                dist[v] = d + costs[v]
                heapq.heappush(pq, (dist[v], v))
    return -1 if dist[n-1] == float('inf') else dist[n-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn min_cost(nums: Vec<i32>, costs: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut nxt_g = vec![-1; n];
    let mut nxt_s = vec![-1; n];
    let mut st = vec![];
    for i in (0..n).rev() {
        while let Some(&j) = st.last() {
            if nums[j] <= nums[i] { st.pop(); } else { break; }
        }
        if let Some(&j) = st.last() { nxt_g[i] = j as i32; }
        st.push(i);
    }
    st.clear();
    for i in (0..n).rev() {
        while let Some(&j) = st.last() {
            if nums[j] >= nums[i] { st.pop(); } else { break; }
        }
        if let Some(&j) = st.last() { nxt_s[i] = j as i32; }
        st.push(i);
    }
    let mut dist = vec![i64::MAX; n];
    dist[0] = costs[0] as i64;
    let mut pq = BinaryHeap::new();
    pq.push(Reverse((dist[0], 0)));
    while let Some(Reverse((d, u))) = pq.pop() {
        if d > dist[u] { continue; }
        for &v in &[nxt_g[u], nxt_s[u]] {
            if v != -1 {
                let v = v as usize;
                if dist[v] > d + costs[v] as i64 {
                    dist[v] = d + costs[v] as i64;
                    pq.push(Reverse((dist[v], v)));
                }
            }
        }
    }
    if dist[n-1] == i64::MAX { -1 } else { dist[n-1] as i32 }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
  minCost(nums: number[], costs: number[]): number {
    const n = nums.length;
    const nxtG = Array(n).fill(-1), nxtS = Array(n).fill(-1);
    let st: number[] = [];
    for (let i = n-1; i >= 0; --i) {
      while (st.length && nums[st[st.length-1]] <= nums[i]) st.pop();
      if (st.length) nxtG[i] = st[st.length-1];
      st.push(i);
    }
    st = [];
    for (let i = n-1; i >= 0; --i) {
      while (st.length && nums[st[st.length-1]] >= nums[i]) st.pop();
      if (st.length) nxtS[i] = st[st.length-1];
      st.push(i);
    }
    const dist = Array(n).fill(Infinity);
    dist[0] = costs[0];
    const pq: [number, number][] = [[dist[0], 0]];
    while (pq.length) {
      pq.sort((a, b) => a[0] - b[0]);
      const [d, u] = pq.shift()!;
      if (d > dist[u]) continue;
      for (const v of [nxtG[u], nxtS[u]]) {
        if (v !== -1 && dist[v] > d + costs[v]) {
          dist[v] = d + costs[v];
          pq.push([dist[v], v]);
        }
      }
    }
    return dist[n-1] === Infinity ? -1 : dist[n-1];
  }
}

Complexity

⏰ Time complexity: O(n log n) — Monotonic stack is O(n), Dijkstra’s algorithm is O(n log n) due to the priority queue.
🧺 Space complexity: O(n) — For stacks, graph, and distance array.

Problem#

Examples#

Solution#

Method 1 – Monotonic Stack + Dijkstra’s Algorithm#

Intuition#

Approach#

Code#

Complexity#