Problem Description

You have an array nums of integers and start at index 0. You want to reach the last index (n-1) by jumping between positions, but there are specific rules about which jumps are allowed.

From any index i, you can jump to a later index j (where i < j) only if one of these conditions is met:

1. Ascending jump: nums[i] <= nums[j] AND all elements between them are strictly less than nums[i]. In other words, nums[i] must be a local maximum compared to all elements between i and j.

2. Descending jump: nums[i] > nums[j] AND all elements between them are greater than or equal to nums[i]. In other words, nums[i] must be a local minimum compared to all elements between i and j.

Each index has an associated cost given in the costs array. When you jump to index j, you must pay costs[j].

Your goal is to find the minimum total cost to reach the last index (n-1) starting from index 0.

For example, if you have nums = [3, 2, 4, 2, 1]:

• From index 0 (value 3), you could jump to index 2 (value 4) because 3 ≤ 4 and the value between them (2) is less than 3.
• From index 0 (value 3), you could also jump to index 4 (value 1) because 3 > 1 and all values between them (2, 4, 2) are ≥ 3... wait, 2 < 3, so this jump would NOT be valid.

The algorithm uses monotonic stacks to efficiently find valid jump destinations for each position, then uses dynamic programming to compute the minimum cost path from index 0 to index n-1.

Intuition

The key insight is recognizing that valid jumps follow a specific pattern: we can only jump to positions that are either the next "peak" or the next "valley" relative to our current position.

Think about what makes a jump valid:

• For an ascending jump (nums[i] <= nums[j]), all intermediate values must be smaller than nums[i]. This means j must be the first position after i where the value rises back up to or above nums[i].
• For a descending jump (nums[i] > nums[j]), all intermediate values must be at least nums[i]. This means j must be the first position after i where the value drops below nums[i].

This observation leads us to realize that from any position i, we can only jump to very specific positions - not just any arbitrary later index. We need to find:

1. The next position where the value is greater than or equal to nums[i] (for ascending jumps)
2. The next position where the value is less than nums[i] (for descending jumps)

Finding these "next greater/smaller element" positions is a classic problem that can be solved efficiently using monotonic stacks. A monotonic stack maintains elements in either increasing or decreasing order, allowing us to find the next element that breaks the pattern in O(n) time.

Once we know all valid jumps from each position, the problem becomes a shortest path problem in a directed graph where:

• Nodes are array indices
• Edges represent valid jumps
• Edge weights are the costs of jumping to the destination index

Since we're looking for minimum cost and can only move forward (from smaller to larger indices), we can use dynamic programming. We track f[i] as the minimum cost to reach index i, starting with f[0] = 0. For each position we can reach, we update its minimum cost based on all positions that can jump to it.

The combination of monotonic stacks (to build the graph) and dynamic programming (to find the minimum cost path) gives us an efficient O(n) solution.

Learn more about Stack, Graph, Dynamic Programming, Shortest Path and Monotonic Stack patterns.

Solution Approach

The solution consists of two main phases: building the jump graph using monotonic stacks, and finding the minimum cost path using dynamic programming.

Phase 1: Building the Jump Graph with Monotonic Stacks

We use two monotonic stacks to find valid jump destinations from each position:

1. Finding next greater or equal elements (for ascending jumps):

   • Traverse the array from right to left
   • Maintain a stack where elements are in decreasing order from bottom to top
   • For each position i, pop elements from the stack while nums[stk[-1]] < nums[i]
   • After popping, if the stack is not empty, stk[-1] is the nearest position to the right where nums[j] >= nums[i]
   • Add this position to the adjacency list g[i]
   • Push current index i onto the stack

2. Finding next smaller elements (for descending jumps):

   • Again traverse from right to left with a fresh stack
   • Maintain a stack where elements are in increasing order from bottom to top
   • For each position i, pop elements while nums[stk[-1]] >= nums[i]
   • After popping, if the stack is not empty, stk[-1] is the nearest position to the right where nums[j] < nums[i]
   • Add this position to g[i]

The monotonic stack approach ensures that for each position i, we find the first valid jump destination to the right that satisfies our conditions. The time complexity for building the graph is O(n) since each element is pushed and popped at most once.

Phase 2: Dynamic Programming for Minimum Cost

With the adjacency list g constructed, we solve for the minimum cost:

• Initialize f[i] = inf for all positions except f[0] = 0 (starting position has no cost)
• Iterate through positions from 0 to n-1
• For each position i, check all positions j in g[i] (positions we can jump to from i)
• Update the minimum cost: f[j] = min(f[j], f[i] + costs[j])
• The answer is f[n-1], the minimum cost to reach the last index

The DP transition works because:

• We process positions in order, ensuring that when we reach position i, we already know the minimum cost to get there
• For each reachable position j from i, we update its minimum cost by considering the path through i
• Since we can only jump forward, this guarantees we find the optimal solution

The overall time complexity is O(n) for building the graph plus O(n + edges) for the DP, where the number of edges is at most 2n (each position can have at most 2 outgoing edges). Thus, the total time complexity is O(n).

Example Walkthrough

Let's trace through a concrete example with nums = [3, 2, 4, 2, 1] and costs = [0, 10, 15, 20, 25].

Phase 1: Building the Jump Graph

Finding next greater or equal elements (ascending jumps):

• Start from right to left with an empty stack
• i=4 (value 1): Stack is empty, no valid jump. Push 4. Stack: [4]
• i=3 (value 2): nums[4]=1 < 2, pop 4. Stack empty, no valid jump. Push 3. Stack: [3]
• i=2 (value 4): nums[3]=2 < 4, pop 3. Stack empty, no valid jump. Push 2. Stack: [2]
• i=1 (value 2): nums[2]=4 ≥ 2, so we can jump from 1→2. Push 1. Stack: [2, 1]
• i=0 (value 3): nums[1]=2 < 3, pop 1. nums[2]=4 ≥ 3, so we can jump from 0→2. Push 0. Stack: [2, 0]

Finding next smaller elements (descending jumps):

• Start from right to left with a fresh empty stack
• i=4 (value 1): Stack empty, no valid jump. Push 4. Stack: [4]
• i=3 (value 2): nums[4]=1 < 2, so we can jump from 3→4. Push 3. Stack: [4, 3]
• i=2 (value 4): nums[3]=2 < 4, so we can jump from 2→3. Push 2. Stack: [4, 3, 2]
• i=1 (value 2): nums[2]=4 ≥ 2, pop 2. nums[3]=2 ≥ 2, pop 3. nums[4]=1 < 2, so we can jump from 1→4. Push 1. Stack: [4, 1]
• i=0 (value 3): nums[1]=2 < 3, so we can jump from 0→1. Push 0. Stack: [4, 1, 0]

Adjacency list g:

• g[0] = [2, 1] (can jump to indices 2 or 1)
• g[1] = [2, 4] (can jump to indices 2 or 4)
• g[2] = [3] (can jump to index 3)
• g[3] = [4] (can jump to index 4)
• g[4] = [] (last index, no jumps)

Phase 2: Dynamic Programming

Initialize f = [0, inf, inf, inf, inf]

• i=0: f[0]=0

  • Jump to j=2: f[2] = min(inf, 0 + 15) = 15
  • Jump to j=1: f[1] = min(inf, 0 + 10) = 10
  • Now f = [0, 10, 15, inf, inf]

• i=1: f[1]=10

  • Jump to j=2: f[2] = min(15, 10 + 15) = 15
  • Jump to j=4: f[4] = min(inf, 10 + 25) = 35
  • Now f = [0, 10, 15, inf, 35]

• i=2: f[2]=15

  • Jump to j=3: f[3] = min(inf, 15 + 20) = 35
  • Now f = [0, 10, 15, 35, 35]

• i=3: f[3]=35

  • Jump to j=4: f[4] = min(35, 35 + 25) = 35
  • Now f = [0, 10, 15, 35, 35]

• i=4: No outgoing edges

The minimum cost to reach index 4 is f[4] = 35, achieved by the path 0→1→4 with total cost 0 + 10 + 25 = 35.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

1. First monotonic stack traversal (lines 5-11): Each element is pushed and popped from the stack at most once, resulting in O(n) operations.

2. Second monotonic stack traversal (lines 13-19): Similarly, each element is pushed and popped at most once, giving O(n) operations.

3. Dynamic programming update (lines 21-24): The outer loop runs n times. For the inner loop, we need to count the total number of edges in graph g. Each index i can have at most 2 neighbors added (one from each stack traversal). Therefore, the total number of edges across all vertices is O(n), making the total work in this section O(n).

Overall time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The space usage includes:

1. Graph g: A defaultdict storing adjacency lists. In the worst case, it stores O(n) edges total, requiring O(n) space.

2. Stack stk: At any point, the stack can contain at most n elements, using O(n) space.

3. DP array f: An array of size n, requiring O(n) space.

Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Jump Conditions

A critical pitfall is misinterpreting what constitutes a valid jump. The monotonic stack approach finds the next greater/equal or smaller element, but this doesn't guarantee all intermediate elements satisfy the jump conditions.

The Problem:

• For an ascending jump from i to j, ALL elements between them must be strictly less than nums[i]
• For a descending jump from i to j, ALL elements between them must be greater than or equal to nums[i]
• The current solution only finds the next element that satisfies the inequality but doesn't verify intermediate elements

Example where this fails:

nums = [3, 1, 4, 2]
# From index 0 (value 3), the next greater/equal is index 2 (value 4)
# But this is NOT a valid ascending jump because we need ALL elements 
# between them (just 1 in this case) to be < 3, which is satisfied.
# However, consider:
nums = [3, 4, 1, 5]
# From index 0 (value 3), next greater/equal is index 1 (value 4)
# This IS a valid jump (no elements between them)
# But from index 0, we cannot jump to index 3 (value 5) even though 3 ≤ 5
# because element at index 1 (value 4) is NOT less than 3

Solution:

def minCost(self, nums: List[int], costs: List[int]) -> int:
    n = len(nums)
    graph = defaultdict(list)
  
    # For each position, find ALL valid jump destinations
    for i in range(n - 1):
        # Check ascending jumps
        for j in range(i + 1, n):
            if nums[i] <= nums[j]:
                # Check if all elements between i and j are < nums[i]
                valid = True
                for k in range(i + 1, j):
                    if nums[k] >= nums[i]:
                        valid = False
                        break
                if valid:
                    graph[i].append(j)
                    break  # Only need the first valid ascending jump
      
        # Check descending jumps  
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                # Check if all elements between i and j are >= nums[i]
                valid = True
                for k in range(i + 1, j):
                    if nums[k] < nums[i]:
                        valid = False
                        break
                if valid:
                    graph[i].append(j)
                    break  # Only need the first valid descending jump
  
    # DP remains the same
    dp = [inf] * n
    dp[0] = 0
    for i in range(n):
        for j in graph[i]:
            dp[j] = min(dp[j], dp[i] + costs[j])
  
    return dp[n - 1]

2. Incorrect Handling of Unreachable Positions

The Problem: If the last index cannot be reached from index 0, the current solution returns inf, which might not be the expected behavior.

Solution: Add validation to check if the destination is reachable:

result = dp[n - 1]
if result == inf:
    return -1  # or raise an exception depending on requirements
return result

3. Stack Order Confusion

The Problem: The monotonic stack maintains a specific order (decreasing or increasing), and it's easy to confuse which comparison to use when popping elements.

Key Points to Remember:

• For finding next greater/equal: Pop while nums[stack[-1]] < nums[i] (maintain decreasing stack)
• For finding next smaller: Pop while nums[stack[-1]] >= nums[i] (maintain increasing stack)

Getting these conditions reversed will result in finding the wrong jump destinations and incorrect results.