2297. Jump Game VIII

MediumStackGraphArrayDynamic ProgrammingShortest PathMonotonic Stack
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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

1from typing import List
2from collections import defaultdict
3from math import inf
4
5class Solution:
6    def min_cost(self, nums: List[int], costs: List[int]) -> int:
7        # Get the number of elements in nums list
8        num_elements = len(nums)
9      
10        # Graph to store edges between elements
11        graph = defaultdict(list)
12      
13        # Monotonic stack to keep track of nearest greater elements from left
14        decreasing_stack = []
15      
16        # Build graph edges based on nearest greater element to the left
17        for i in range(num_elements - 1, -1, -1):
18            # Ensure stack elements are greater than the current element
19            while decreasing_stack and nums[decreasing_stack[-1]] < nums[i]:
20                decreasing_stack.pop()
21            # If stack not empty, make a connection in graph
22            if decreasing_stack:
23                graph[i].append(decreasing_stack[-1])
24            # Add current index to stack
25            decreasing_stack.append(i)
26
27        # Clear stack to reuse it
28        decreasing_stack.clear()
29      
30        # Build graph edges based on nearest greater element to the right
31        for i in range(num_elements - 1, -1, -1):
32            # Ensure stack elements are greater than or equal to the current element
33            while decreasing_stack and nums[decreasing_stack[-1]] >= nums[i]:
34                decreasing_stack.pop()
35            # If stack not empty, make a connection in graph
36            if decreasing_stack:
37                graph[i].append(decreasing_stack[-1])
38            # Add current index to stack
39            decreasing_stack.append(i)
40
41        # Initialize cost array with infinity and 0 for the start position
42        cost_array = [inf] * num_elements
43        cost_array[0] = 0
44      
45        # Calculate the minimum cost to reach each node
46        for i in range(num_elements):
47            for j in graph[i]:
48                cost_array[j] = min(cost_array[j], cost_array[i] + costs[j])
49      
50        # Return the minimum cost to reach the last node
51        return cost_array[num_elements - 1]
52
1class Solution {
2  
3    public long minCost(int[] nums, int[] costs) {
4        // Get the length of the nums array.
5        int n = nums.length;
6      
7        // Initialize an array of Lists to hold the graph edges.
8        List<Integer>[] graph = new List[n];
9        Arrays.setAll(graph, k -> new ArrayList<>());
10
11        // Declare a stack to process greater elements.
12        Deque<Integer> stack = new ArrayDeque<>();
13
14        // Construct the graph edges for each element looking for the next greater element.
15        for (int i = n - 1; i >= 0; --i) {
16            // Pop elements from the stack until we find a greater element.
17            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
18                stack.pop();
19            }
20            // If stack is not empty, then next greater element exists.
21            if (!stack.isEmpty()) {
22                graph[i].add(stack.peek());
23            }
24            stack.push(i);
25        }
26
27        // Clear the stack to reuse it.
28        stack.clear();
29      
30        // Construct the graph edges for each element looking for the next greater or equal element.
31        for (int i = n - 1; i >= 0; --i) {
32            // Pop elements from the stack as long as the current element is greater than or equal.
33            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
34                stack.pop();
35            }
36            // If stack is not empty, then next greater or equal element exists.
37            if (!stack.isEmpty()) {
38                graph[i].add(stack.peek());
39            }
40            stack.push(i);
41        }
42
43        // Initialize a dynamic programming array for storing minimum costs.
44        long[] minCosts = new long[n];
45        // Set all values to a large number to represent infinity (unprocessed state).
46        Arrays.fill(minCosts, Long.MAX_VALUE);
47        // Start condition: cost at the first index (0) is 0.
48        minCosts[0] = 0;
49      
50        // Process all elements to compute minimum path costs.
51        for (int i = 0; i < n; ++i) {
52            // Propagate cost to the next connected nodes.
53            for (int j : graph[i]) {
54                minCosts[j] = Math.min(minCosts[j], minCosts[i] + costs[j]);
55            }
56        }
57      
58        // Return the minimum cost to reach the end of the array (n - 1).
59        return minCosts[n - 1];
60    }
61}
62
1class Solution {
2public:
3    // Find the minimum cost to change the array into a non-decreasing array
4    long long minCost(vector<int>& nums, vector<int>& costs) {
5        int n = nums.size();
6        // Adjacency list to depict the graph
7        vector<int> graph[n];
8        stack<int> stk;
9      
10        // Build the graph for the next greater element to the left
11        for (int i = n - 1; i >= 0; --i) {
12            // Pop elements from the stack until the current element is greater
13            while (!stk.empty() && nums[stk.top()] < nums[i]) {
14                stk.pop();
15            }
16            // If the stack is not empty, a greater element exists, add an edge 
17            if (!stk.empty()) {
18                graph[i].push_back(stk.top());
19            }
20            stk.push(i);
21        }
22      
23        // Clear the stack to reuse it for the next non-greater element to the left
24        stk = stack<int>();
25      
26        // Build the graph for the next non-greater element to the left
27        for (int i = n - 1; i >= 0; --i) {
28            // Pop elements until a non-greater element is found
29            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
30                stk.pop();
31            }
32            // If the stack is not empty, add an edge to the graph
33            if (!stk.empty()) {
34                graph[i].push_back(stk.top());
35            }
36            stk.push(i);
37        }
38      
39        // Dynamic programming array to store the minimum cost to reach each element
40        vector<long long> dp(n, 1e18);
41        // Starting cost is 0
42        dp[0] = 0;
43      
44        // Loop through the array to calculate the minimum cost for each position
45        for (int i = 0; i < n; ++i) {
46            for (int j : graph[i]) {
47                // Update the cost of reaching an adjacent node
48                dp[j] = min(dp[j], dp[i] + costs[j]);
49            }
50        }
51      
52        // Return the minimum cost to reach the last element
53        return dp[n - 1];
54    }
55};
56
1// Function to calculate minimum cost to reach end of the array
2function minCost(nums: number[], costs: number[]): number {
3    const n = nums.length;
4    // g will hold for each element at i, the indices of the elements we can jump to
5    const graph: number[][] = Array.from({ length: n }, () => []);
6    // stack is used to keep track of the increasing numbers sequence
7    const stack: number[] = [];
8
9    // Iterate from the end to start to populate the graph with possible jumps
10    for (let i = n - 1; i >= 0; --i) {
11        // Remove elements from the stack that are less than the current element
12        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
13            stack.pop();
14        }
15        // If stack is not empty, current element can jump to element at index stack[stack.length - 1]
16        if (stack.length) {
17            graph[i].push(stack[stack.length - 1]);
18        }
19        // Push current index to the stack
20        stack.push(i);
21    }
22
23    // Reset stack to be used for the second condition
24    stack.length = 0;
25
26    // Populate the graph for the second condition: the next greater or equal element
27    for (let i = n - 1; i >= 0; --i) {
28        // Remove elements from the stack that are greater than or equal to the current element
29        while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
30            stack.pop();
31        }
32        // If stack is not empty, current element can jump to element at index stack[stack.length - 1]
33        if (stack.length) {
34            graph[i].push(stack[stack.length - 1]);
35        }
36        // Push current index to the stack
37        stack.push(i);
38    }
39
40    // f[i] will store the minimum cost to reach element i
41    const minCosts: number[] = Array.from({ length: n }, () => Infinity);
42    // The cost of starting at the first element is 0
43    minCosts[0] = 0;
44
45    // Iterate over the graph to calculate minimum cost based on the jumps available
46    for (let i = 0; i < n; ++i) {
47        for (const j of graph[i]) {
48            // f[j] is the minimum cost to reach j, either the existing cost or a new cost comes from i plus the cost at j
49            minCosts[j] = Math.min(minCosts[j], minCosts[i] + costs[j]);
50        }
51    }
52  
53    // The minimum cost to reach the last element is at n-1 position in minCosts
54    return minCosts[n - 1];
55}
56
Not Sure What to Study? Take the 2-min Quiz

Which of these properties could exist for a graph but not a tree?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«