LeetCode 2297 - Jump Game VIII

LeetCode Problem 2297

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Stack, Graph Theory, Monotonic Stack, Shortest Path

Solution

Problem Understanding

This problem asks us to compute the minimum total cost required to move from index 0 to index n - 1 in an array. The movement rules are unusual because whether a jump is valid depends not only on the values at the start and destination indices, but also on every element in between.

We are given two arrays:

• nums[i] describes the value at index i
• costs[i] describes the cost paid when landing on index i

You begin at index 0, and you do not pay costs[0] because you start there. Every time you jump to another index j, you pay costs[j].

A jump from index i to index j where i < j is valid if one of the following conditions holds:

1. nums[i] <= nums[j], and every value between them is strictly smaller than nums[i]
2. nums[i] > nums[j], and every value between them is greater than or equal to nums[i]

The challenge is to determine the minimum possible total landing cost to reach the final index.

The constraints are important:

• n can be as large as 100000
• A naive graph construction that checks every pair (i, j) would require O(n^2) work
• We therefore need an algorithm close to linear or O(n log n)

The key difficulty is efficiently determining which jumps are valid.

Several edge cases are important:

• Strictly increasing arrays
• Strictly decreasing arrays
• Arrays with repeated values
• Situations where many indices appear reachable
• Very large inputs where quadratic processing would time out

The problem guarantees that all values are non negative and that the arrays have equal length.

Approaches

Brute Force Approach

The most direct interpretation is to model the problem as a graph.

Each index is a node. For every pair (i, j) with i < j, we check whether the jump conditions are satisfied. If the jump is valid, we add a directed edge from i to j with weight costs[j].

Once the graph is built, we can run a shortest path algorithm such as Dijkstra's algorithm or dynamic programming over the DAG.

This approach is correct because it explicitly models every legal move and computes the minimum path cost through the graph.

The problem is that validating all pairs requires O(n^2) checks. Worse, each check may scan the subarray between i and j, producing even larger complexity.

With n = 100000, this is completely infeasible.

Key Insight

The jump rules actually describe visibility relationships that can be discovered using monotonic stacks.

For every index, only certain nearby elements matter:

• The next greater or equal element
• The next smaller element

These are classic monotonic stack patterns.

The crucial observation is that if a jump skips over another candidate, then the skipped candidate blocks future jumps because the jump conditions require all intermediate elements to obey strict ordering constraints.

This means each index only needs edges to a small number of neighboring indices discovered through monotonic stacks.

Once we identify these valid transitions efficiently, the problem becomes a shortest path dynamic programming problem.

We process indices from left to right and maintain:

• A monotonic decreasing stack
• A monotonic increasing stack
• A DP array where dp[i] is the minimum cost to reach index i

Each stack operation creates valid transitions while preserving the jump conditions.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(n²)	Explicitly checks all jumps
Optimal	O(n)	O(n)	Uses monotonic stacks and dynamic programming

Algorithm Walkthrough

1. Create a DP array dp of length n.

dp[i] represents the minimum cost required to reach index i.

Initialize every value to infinity except dp[0] = 0 because we start at index 0 without paying any cost. 2. Maintain a decreasing monotonic stack.

This stack stores indices whose nums values are strictly decreasing.

While processing index i, if nums[stack[-1]] <= nums[i], then we can jump from that stack index to i.

Why does this work?

Because every element between them is smaller than the source value. Otherwise, the stack structure would already have removed the source index earlier. 3. For every popped index from the decreasing stack, update:

dp[i] = min(dp[i], dp[popped] + costs[i])

This means we are considering a jump from popped to i. 4. After popping, if the stack is still non empty, the top element can also jump to i.

This represents the nearest larger element to the left that satisfies the second jump condition. 5. Push the current index i onto the decreasing stack. 6. Maintain an increasing monotonic stack similarly.

This stack stores indices whose nums values are strictly increasing.

While nums[stack[-1]] > nums[i], pop indices and attempt transitions. 7. For every popped index in the increasing stack, update:

dp[i] = min(dp[i], dp[popped] + costs[i]) 8. After popping, if the stack is still non empty, its top can also transition to i. 9. Push the current index onto the increasing stack. 10. Continue until all indices are processed. 11. Return dp[n - 1].

Why it works

The monotonic stacks guarantee that every valid transition implied by the jump rules is considered exactly once.

The decreasing stack handles jumps where the destination is greater than or equal to the source value. The increasing stack handles jumps where the destination is smaller.

The stack invariants ensure that any blocked or invalid transitions are automatically excluded. Since every valid edge is processed and the DP recurrence always keeps the minimum achievable cost, the final answer is optimal.

Python Solution

from typing import List

class Solution:
    def minCost(self, nums: List[int], costs: List[int]) -> int:
        n = len(nums)

        dp = [float("inf")] * n
        dp[0] = 0

        decreasing_stack = []
        increasing_stack = []

        for i in range(n):

            while decreasing_stack and nums[decreasing_stack[-1]] <= nums[i]:
                prev = decreasing_stack.pop()
                dp[i] = min(dp[i], dp[prev] + costs[i])

            if decreasing_stack:
                dp[i] = min(dp[i], dp[decreasing_stack[-1]] + costs[i])

            decreasing_stack.append(i)

            while increasing_stack and nums[increasing_stack[-1]] > nums[i]:
                prev = increasing_stack.pop()
                dp[i] = min(dp[i], dp[prev] + costs[i])

            if increasing_stack:
                dp[i] = min(dp[i], dp[increasing_stack[-1]] + costs[i])

            increasing_stack.append(i)

        return dp[-1]

The implementation follows the algorithm directly.

The dp array stores the minimum cost to reach each position. Initially, every index is unreachable except index 0.

Two monotonic stacks are maintained simultaneously.

The decreasing stack processes transitions where the destination value is greater than or equal to the source value. While the top element is less than or equal to the current value, it can legally jump to the current index, so we pop it and update the DP state.

After the popping phase, the remaining top element is the nearest larger value to the left, which also satisfies the alternate jump condition.

The increasing stack works symmetrically for transitions where the destination value is smaller.

Each index is pushed and popped at most once from each stack, which guarantees linear time complexity.

Go Solution

func minCost(nums []int, costs []int) int64 {
	n := len(nums)

	const INF int64 = 1 << 60

	dp := make([]int64, n)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = 0

	decreasingStack := []int{}
	increasingStack := []int{}

	for i := 0; i < n; i++ {

		for len(decreasingStack) > 0 &&
			nums[decreasingStack[len(decreasingStack)-1]] <= nums[i] {

			prev := decreasingStack[len(decreasingStack)-1]
			decreasingStack = decreasingStack[:len(decreasingStack)-1]

			if dp[prev]+int64(costs[i]) < dp[i] {
				dp[i] = dp[prev] + int64(costs[i])
			}
		}

		if len(decreasingStack) > 0 {
			prev := decreasingStack[len(decreasingStack)-1]

			if dp[prev]+int64(costs[i]) < dp[i] {
				dp[i] = dp[prev] + int64(costs[i])
			}
		}

		decreasingStack = append(decreasingStack, i)

		for len(increasingStack) > 0 &&
			nums[increasingStack[len(increasingStack)-1]] > nums[i] {

			prev := increasingStack[len(increasingStack)-1]
			increasingStack = increasingStack[:len(increasingStack)-1]

			if dp[prev]+int64(costs[i]) < dp[i] {
				dp[i] = dp[prev] + int64(costs[i])
			}
		}

		if len(increasingStack) > 0 {
			prev := increasingStack[len(increasingStack)-1]

			if dp[prev]+int64(costs[i]) < dp[i] {
				dp[i] = dp[prev] + int64(costs[i])
			}
		}

		increasingStack = append(increasingStack, i)
	}

	return dp[n-1]
}

The Go solution mirrors the Python logic closely.

One important difference is that the return type is int64, so the DP array also uses int64 to avoid overflow concerns when accumulating costs.

Go slices are used as stacks. Popping is implemented by reslicing with stack[:len(stack)-1].

Unlike Python, Go does not provide infinity values for integers, so a very large constant is used instead.

Worked Examples

Example 1

Input:

nums  = [3,2,4,4,1]
costs = [3,7,6,4,2]

Initial state:

Index	dp
0	0
1	inf
2	inf
3	inf
4	inf

Iteration i = 0

Structure	State
decreasingStack	[0]
increasingStack	[0]

Iteration i = 1

nums[0] > nums[1], so the increasing stack allows a transition.

dp[1] = dp[0] + costs[1] = 7

Structure	State
dp	[0, 7, inf, inf, inf]
decreasingStack	[0, 1]
increasingStack	[1]

Iteration i = 2

nums[1] <= nums[2], pop from decreasing stack.

Transition:

1 -> 2
cost = 7 + 6 = 13

Then:

nums[0] <= nums[2]

Transition:

0 -> 2
cost = 0 + 6 = 6

Best value:

dp[2] = 6

Structure	State
dp	[0, 7, 6, inf, inf]
decreasingStack	[2]
increasingStack	[1, 2]

Iteration i = 3

nums[2] <= nums[3]

Transition:

2 -> 3
cost = 6 + 4 = 10

Best:

dp[3] = 10

Structure	State
dp	[0, 7, 6, 10, inf]

Iteration i = 4

Using increasing stack transitions:

3 -> 4 = 12
2 -> 4 = 8
1 -> 4 = 9

Best:

dp[4] = 8

Final answer:

8

Example 2

Input:

nums  = [0,1,2]
costs = [1,1,1]

Iteration i = 0

Stacks:

Stack	State
decreasing	[0]
increasing	[0]

Iteration i = 1

0 <= 1

Transition:

0 -> 1
cost = 1

dp
[0, 1, inf]

Iteration i = 2

Direct jump from 0 to 2 is invalid because nums[1] is not smaller than nums[0].

Valid transition:

1 -> 2
cost = 2

Final:

dp
[0, 1, 2]

Answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every index is pushed and popped at most once from each stack
Space	O(n)	DP array and stacks require linear storage

The linear time complexity comes from the amortized behavior of monotonic stacks. Although the inner loops appear nested, each index can only be removed from a stack once, so the total number of stack operations is proportional to n.

Test Cases

from typing import List

class Solution:
    def minCost(self, nums: List[int], costs: List[int]) -> int:
        n = len(nums)

        dp = [float("inf")] * n
        dp[0] = 0

        decreasing_stack = []
        increasing_stack = []

        for i in range(n):

            while decreasing_stack and nums[decreasing_stack[-1]] <= nums[i]:
                prev = decreasing_stack.pop()
                dp[i] = min(dp[i], dp[prev] + costs[i])

            if decreasing_stack:
                dp[i] = min(dp[i], dp[decreasing_stack[-1]] + costs[i])

            decreasing_stack.append(i)

            while increasing_stack and nums[increasing_stack[-1]] > nums[i]:
                prev = increasing_stack.pop()
                dp[i] = min(dp[i], dp[prev] + costs[i])

            if increasing_stack:
                dp[i] = min(dp[i], dp[increasing_stack[-1]] + costs[i])

            increasing_stack.append(i)

        return dp[-1]

sol = Solution()

assert sol.minCost([3,2,4,4,1], [3,7,6,4,2]) == 8
# Provided example with mixed jumps

assert sol.minCost([0,1,2], [1,1,1]) == 2
# Strictly increasing array

assert sol.minCost([5], [10]) == 0
# Single element, already at destination

assert sol.minCost([5,4,3,2,1], [1,1,1,1,1]) == 4
# Strictly decreasing array

assert sol.minCost([1,2,3,4,5], [5,4,3,2,1]) == 10
# Strictly increasing array with varying costs

assert sol.minCost([2,2,2], [1,2,3]) == 5
# Equal values

assert sol.minCost([10,1,10], [1,5,1]) == 1
# Direct jump skipping middle element

assert sol.minCost([4,1,3,2], [1,2,3,4]) == 6
# Mixed transitions

assert sol.minCost([1,100000,1], [1,1,1]) == 2
# Large value differences

Test Summary

Test	Why
[3,2,4,4,1]	Validates mixed increasing and decreasing transitions
[0,1,2]	Confirms direct jump blocking behavior
[5]	Smallest possible input
[5,4,3,2,1]	Tests decreasing monotonic behavior
[1,2,3,4,5]	Tests increasing monotonic behavior
[2,2,2]	Ensures equal values are handled correctly
[10,1,10]	Verifies long jumps skipping valleys
[4,1,3,2]	Exercises both stacks together
[1,100000,1]	Tests large numeric ranges

Edge Cases

Single Element Array

If n = 1, we already begin at the destination index. No jumps are required, so the minimum cost must be 0.

This is easy to mishandle if the implementation assumes at least one transition occurs. The DP initialization correctly handles this because dp[0] starts at 0 and the loop never changes it.

Repeated Values

Arrays with duplicate values are subtle because the jump conditions use both < and <=.

For example:

nums = [2,2,2]

The monotonic stack conditions must carefully preserve equality behavior. The decreasing stack uses <= while the increasing stack uses > so that equal values are processed consistently and no valid transitions are lost.

Strictly Monotonic Arrays

Strictly increasing and strictly decreasing arrays stress one stack heavily while the other remains mostly unused.

For increasing arrays, the decreasing stack repeatedly pops elements. For decreasing arrays, the increasing stack repeatedly pops elements.

A buggy implementation may accidentally produce quadratic behavior here, but the monotonic stack approach guarantees each index is processed only once per stack, preserving linear complexity.