3221. Maximum Array Hopping Score II 🔒

Problem Description

Given an array nums, you have to get the maximum score starting from index 0 and hopping until you reach the last element of the array.

In each hop, you can jump from index i to an index j > i, and you get a score of (j - i) * nums[j].

Return the maximum score you can get.

Intuition

The goal is to maximize the score by cleverly choosing which indices to hop to. The score for each hop depends both on the distance between the indices and the value at the target index. To maximize the score starting from index 0, we should try to maximize the value at the index we jump to, while accounting for the distance.

The given solution uses a monotonic stack to keep track of potential target indices. The idea is to maintain a stack where values are stored in a descending order from top to bottom, guaranteeing that each new index considered gives a score improvement.

Here's the step-by-step intuition:

Traverse through the array and maintain a monotonically decreasing stack. This stack keeps indices of the elements in a way that allows us to quickly decide which index to jump to next for a better score.
For each new element, if its value is larger than the element at the index represented by the top of the stack, remove indices from the stack until the current element becomes the largest in the stack.
Once you prepare a decreasing stack of indices representing the potential hops, calculate the scores by iterating through the stack.
Start from the base index, jump to the index represented by the top of the stack, and add the score to your ongoing sum. The (j - i) * nums[j] formula ensures that both the distance and the element value contribute to the score.

By choosing a jumping strategy that maximizes scores at each step, and systematically eliminating indices that don't contribute to higher scores, this approach efficiently finds the maximum score possible.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

The solution leverages a monotonic stack to efficiently decide which indices to hop to for maximizing the score. Here is how the solution is implemented:

Initialize the Stack: Begin with an empty list stk that will function as our stack. This stack will help us keep track of indices with values that provide potential hops to increase our score.
Building the Monotonic Stack:
- Traverse through the array nums using a loop and access each element x with its index i.
- As you iterate, check if the stack is not empty and if the element at the top of the stack is less than or equal to the current element x.
- If the top element of the stack is less or equal, pop this element. This ensures that the stack remains in decreasing order.
- Finally, append the current index i to the stack.
Calculating the Maximum Score:
- Initialize ans to store the maximum score and set i to 0, which represents the current base index.
- Iterate through each index j in the stack.
- Apply the formula to update the score: ans += nums[j] * (j - i). This formula computes the contribution of a hop to the overall score.
- Update the base index i to the current index j of the stack. Repeat this process for each element in the stack to accumulate the total maximum score.

The use of a monotonic stack allows the algorithm to efficiently determine the sequence of jumps that maximize the score without revisiting indices, ensuring a time-efficient solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with an array nums = [3, 6, 2, 8, 4, 5]. We'll walk through how to use the monotonic stack to calculate the maximum score.

Initial Setup

Create the Stack: Start with an empty stack, stk = [].
Initialize Variables: Set ans to 0, as the accumulative score, and i to 0, representing the starting index.

Building the Monotonic Stack

Loop through each index and element in nums:

Index 0, Value 3:
- stk is empty; append 0.
  stk = [0]
Index 1, Value 6:
- 6 > 3, so pop 0 from the stack.
- Append 1 to maintain a decreasing order in values. stk = [1]
Index 2, Value 2:
- 2 < 6, append 2.
  stk = [1, 2]
Index 3, Value 8:
- 8 > 2, pop 2.
- 8 > 6, pop 1.
- Append 3, as 8 is now the largest.
  stk = [3]
Index 4, Value 4:
- 4 < 8, append 4. stk = [3, 4]
Index 5, Value 5:
- 5 > 4, pop 4.
- Append 5.
  stk = [3, 5]

Calculating the Maximum Score

Now, iterate through indices in the stk:

Jump to Index 3:
- Calculate (3 - 0) * nums[3] = 3 * 8 = 24.
- Update ans = 24, set i = 3.
Jump to Index 5:
- Calculate (5 - 3) * nums[5] = 2 * 5 = 10.
- Update ans = 24 + 10 = 34, set i = 5.

The maximum score achieved by hopping through this array is 34. Using this example, the strategy involves choosing jumps that maximize both the value of nums[j] and the distance (j - i) in each step.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxScore(self, nums: List[int]) -> int:
5        # This stack will store indices of elements in nums that are part of the calculation
6        stack = []
7      
8        # Enumerate through each element in the nums list
9        for index, value in enumerate(nums):
10            # Ensure stack is non-empty and the last element in nums accessed by stack is less than or equal to current value
11            while stack and nums[stack[-1]] <= value:
12                stack.pop()
13            # Add current index to the stack
14            stack.append(index)
15      
16        # Initialize answer and a variable `i` for tracking previous index
17        ans = i = 0
18      
19        # Iterate through the indices stored in the stack
20        for j in stack:
21            # Calculate the score using elements in indices of nums between i and j, inclusive of j only
22            ans += nums[j] * (j - i)
23            # Update previous index `i` to current index `j`
24            i = j
25      
26        # Return the final calculated score
27        return ans
28

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    public long maxScore(int[] nums) {
6        // Initialize a stack to keep track of indices of elements in non-increasing order
7        Deque<Integer> stack = new ArrayDeque<>();
8      
9        // Iterate through the array
10        for (int index = 0; index < nums.length; ++index) {
11            // Pop elements from the stack as long as the current element is greater than
12            // or equal to the element at the top of the stack
13            while (!stack.isEmpty() && nums[stack.peek()] <= nums[index]) {
14                stack.pop();
15            }
16            // Push the current index onto the stack
17            stack.push(index);
18        }
19      
20        // Initialize answer and index variables
21        long answer = 0, startIndex = 0;
22      
23        // Process the remaining indices in the stack
24        while (!stack.isEmpty()) {
25            int endIndex = stack.pollLast(); // Get the last element in the stack
26            answer += (endIndex - startIndex) * nums[endIndex]; // Add to the score
27            startIndex = endIndex; // Update the start index
28        }
29      
30        return answer; // Return the computed maximum score
31    }
32}
33

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    long long maxScore(vector<int>& nums) {
7        // Initialize a stack to store indices.
8        vector<int> stack;
9
10        // Loop through each element in the 'nums' vector.
11        for (int i = 0; i < nums.size(); ++i) {
12            // Maintain stack order by popping elements that are less than or equal to the current element.
13            while (!stack.empty() && nums[stack.back()] <= nums[i]) {
14                stack.pop_back();
15            }
16            // Push the current index onto the stack.
17            stack.push_back(i);
18        }
19
20        long long result = 0;
21        long long prevIndex = 0;
22
23        // Calculate the maximum score using the indices stored in the stack.
24        for (int index : stack) {
25            // Increment the result with the product of the range and the corresponding value.
26            result += (index - prevIndex) * static_cast<long long>(nums[index]);
27            // Update the previous index to the current index.
28            prevIndex = index;
29        }
30
31        // Return the final calculated maximum score.
32        return result;
33    }
34};
35

1function maxScore(nums: number[]): number {
2    // Stack to store indices of the nums array
3    const stack: number[] = [];
4
5    // Fill the stack with indices such that the value at these indices is in decreasing order
6    for (let index = 0; index < nums.length; ++index) {
7        // Pop elements from the stack as long as
8        // the current number is greater than or equal to the number at the top of the stack
9        while (stack.length && nums[stack.at(-1)!] <= nums[index]) {
10            stack.pop();
11        }
12        // Push current index onto the stack
13        stack.push(index);
14    }
15
16    let accumulatedScore = 0; // This will hold the total score
17    let lastIndex = 0;        // Track the last processed index in the stack
18
19    // Calculate the score using the indices stored in the stack
20    for (const currentIndex of stack) {
21        // Calculate the score for the segment from lastIndex to currentIndex
22        accumulatedScore += (currentIndex - lastIndex) * nums[currentIndex];
23        // Update lastIndex to the current index
24        lastIndex = currentIndex;
25    }
26
27    return accumulatedScore; // Return the final accumulated score
28}
29

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This is because each element is pushed and popped from the stack at most once, resulting in linear time operations over the entire list.

The space complexity is O(n) as well, due to the extra space used by the stack stk, which can hold indices of up to all elements in nums in the worst case.

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

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

Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don’t know