Problem Description

In this problem, you are given an integer array nums of length n where you are initially at the 0th index. The goal is to reach the last index (n-1) by jumping between indices under certain conditions. You can jump from an index i to an index j (where i < j) only if the following conditions are met:

• nums[i] <= nums[j] and all elements nums[k] for i < k < j are strictly less than nums[i], OR
• nums[i] > nums[j] and all elements nums[k] for i < k < j are greater than or equal to nums[i].

Additionally, you're provided with a costs array where costs[i] represents the cost to jump to index i. The task is to determine the minimum cost to reach the last index n - 1 from the 0th index.

Intuition

To solve this problem, we can utilize a dynamic programming approach. The intuition behind the solution is to build up the information from the starting index to the end, finding the minimum cost to reach each index j from any possible index i. We'll be approaching this in a backward fashion, starting from the last index and moving towards the first index, tracking the valid jumps and their corresponding costs.

First, we will identify all the valid jumps for each index. For example, an index i can jump to another index j if it satisfies one of the two conditions given. To find these valid jumps efficiently, we can use a monotonic stack that helps us find the next greater or the next smaller elements.

After discovering all possible jumps, we'll use another list, let's say f, where f[i] represents the minimum cost to reach the index i. Initially, the cost of reaching the starting index (0th index) is set to 0, and the cost of reaching all other indices is set to infinity. We iteratively update the costs of reaching each index by considering the costs of all previous indices from which a jump to the current index is valid, ensuring we're choosing the minimum possible cost.

By the end of the process, f[n - 1] will hold the minimum cost to reach the last index, which is what we need to return.

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

Solution Approach

The key to the solution lies in understanding how to use the stack data structure to keep track of the valid jumps efficiently, and how to use dynamic programming to calculate the minimum cost to reach each index.

Stack for Tracking Jumps

The solution involves building two sets of potential jumps: one for when nums[i] <= nums[j] and another for when nums[i] > nums[j]. For this, we use a stack, which maintains indices in a specific order allowing us to quickly identify the next index that satisfies the required conditions.

• Descending Stack for nums[i] <= nums[j] Jumps: We iterate backward through the array. For each number, we pop from the stack until we find a number larger than the current one — this represents a valid jump. The condition nums[i] <= nums[j] ensures we're looking for the next larger number, hence a descending stack.

• Ascending Stack for nums[i] > nums[j] Jumps: Similarly, we iterate backward but pop the elements which are larger than or equal to the current number. This finds the next smaller element, corresponding to a jump where nums[i] > nums[j].

At each step, we save the possible jumps in a graph g, where g[i] represents a list containing indices j to which i can jump.

Dynamic Programming for Minimum Cost Calculation

Dynamic programming comes into play for calculating the minimum cost. We initialize a list f where f[i] represents the minimum cost to jump to index i. The base case is f[0] = 0 since it costs nothing to start at the first index. We then loop through each index i and for each potential jump j that can be made from i, we update f[j] to be the minimum of its current value and the cost to jump to j from i plus costs[j].

The recurrence relation is f[j] = min(f[j], f[i] + costs[j]). This ensures that we're always tracking the least cost to reach index j.

Result

The algorithm above runs in O(n) time since each element is pushed and popped from the stack at most once, and the dynamic programming step involves visiting each edge (jump) in the graph g. The space complexity is O(n) because we store information for each index in various lists and the graph. The final answer is f[n - 1], which gives us the minimum cost to reach the last index.

Example Walkthrough

Let's consider a small example to illustrate the solution approach with an array nums and a corresponding costs array.

Suppose nums = [4, 3, 1, 5, 2] and costs = [5, 6, 1, 3, 4].

The goal is to find the minimum cost to reach the last index of nums from the first index.

Step 1: Descending Stack for nums[i] <= nums[j] Jumps

We initialize an empty descending stack and go backwards through the nums array to identify valid jumps for the case where nums[i] <= nums[j].

For index 4 (last index), stack is []. No previous elements, so we move on.

For index 3 (nums[3] = 5), stack is [4]. nums[3] > nums[4], so we pop the stack. Now stack is [] and we push index 3 onto it.

For index 2 (nums[2] = 1), stack is [3]. nums[2] can jump to index 3 following nums[i] <= nums[j].

Continue this process through the array:

• For index 1, stack is [3, 2]; 1 cannot jump to 3 or 2 since nums[1] > nums[2] and nums[1] > nums[3].
• For index 0, stack is [3, 2]; 4 can jump to both 2 and 3 because nums[0] <= nums[3] and nums[0] <= nums[2]

Step 2: Ascending Stack for nums[i] > nums[j] Jumps

Now, we use an ascending stack for identifying jumps where nums[i] > nums[j]. Repeat the process with a new stack.

For index 4, stack is [].

For index 3, stack is [] and we push 3 onto it.

For index 2, stack is [3]. Since nums[2] < nums[3], push index 2 onto the stack.

For index 1, stack is [3, 2]; pop the stack since 1 is greater than 2 (both 1 and 3 are popped). Stack is now [].

For index 0, stack is []. No jumps possible for this case.

Step 3: Dynamic Programming for Minimum Cost Calculation

Now we calculate the minimum cost to each index from 0. Initialize f with infinity: f = [inf, inf, inf, inf, inf], and f[0] = 0.

Starting with index 0, we can jump to index 2 and 3.

• To jump to index 2, cost is f[2] = f[0] + costs[2] = 0 + 1 = 1.
• To jump to index 3, cost is f[3] = f[0] + costs[3] = 0 + 3 = 3.

Moving to index 1, no jumps are possible as identified earlier, so skip to index 2.

From index 2, we can jump to index 3:

• The new cost to index 3 is f[3] = min(f[3], f[2] + costs[3]) = min(3, 1 + 3) = 4.
  However, this is not the minimum as we already had a cost of 3 to reach index 3.

There are no valid jumps from index 3.

The minimum cost to reach the last index (f[4]) is the minimum of jumps to index 4 from all possible indices before it. Since we haven't identified any valid jumps, the cost will be just the cost of jumping to it, which is costs[4]. So f[4] = costs[4].

Result

Thus, the minimum cost to reach the last index is the cost to index 4, which is f[4] = 4.

So the answer is 4.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed by examining the two main parts of the algorithm: graph construction and dynamic programming.

1. Graph Construction: There are two similar loops that iterate backward through the input list nums, from n - 1 to 0. Each loop performs a constant amount of work for each element by comparing against elements in a stack and updating the graph g. The worst-case time complexity for each of these loops is O(n), because each element is pushed to and popped from the stack at most once.

2. Dynamic Programming: After building the graph, the algorithm iterates over each element in the list nums and updates the minimum cost for each connected node. Since each node can have at most two connections (because in the worst case, there’s a connection to the next greater element and next smaller or equal element), and there are n nodes, the loop iterates at most 2n times. Within this loop, the cost calculation is constant time.

Combining both parts, the total time complexity of the entire algorithm is O(n + 2n), which simplifies to O(n).

Space Complexity

The space complexity is determined by the additional space required for the data structures used in the algorithm:

1. Graph Representation (g): The graph g is represented using a defaultdict of lists, which can potentially contain up to 2n edges (in the form of list items), where n is the number of elements in the input list nums.

2. Stacks (stk): Two stacks are used in the graph construction, and each can contain up to n indices at any one time.

3. Dynamic Programming Array (f): A list f of length n is used to store the minimum cost up to that point.

Taking all these into consideration, the space complexity is O(n + 2n + n), which simplifies to O(n) since constants are dropped in Big O notation.

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