Is Maximum Array Hopping Score II easy or hard?

Maximum Array Hopping Score II is rated Medium difficulty. The scoring rule is simple, but recognizing that a monotonic stack can eliminate inferior jump options requires familiarity with advanced array optimization patterns.

Maximum Array Hopping Score II Python/Java solution

Most implementations follow the same pattern: iterate through the array, maintain a monotonic stack of indices, and compute scores using the formula (j - i) * nums[i]. The algorithm translates directly into Python, Java, C++, Go, and TypeScript with identical O(n) complexity.

How to solve Maximum Array Hopping Score II in O(n)?

Use a monotonic decreasing stack while processing indices from right to left. Remove future indices with smaller values since they produce weaker continuation scores. The next remaining index on the stack becomes the best jump target, allowing you to compute the score in constant time per element.

What is the best approach for Maximum Array Hopping Score II?

The optimal approach uses a greedy strategy with a monotonic stack. By scanning the array and maintaining candidate jump positions in decreasing order, you can determine the best next hop for each index without checking every possibility. This reduces the complexity from O(n²) to O(n) while still computing the maximum score.

Is Maximum Array Hopping Score II asked at Google/Amazon/Meta?

Problems involving monotonic stacks and greedy array traversal frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the pattern of using a monotonic stack to eliminate dominated candidates is commonly tested.

What data structure is used in Maximum Array Hopping Score II?

The key data structure is a monotonic stack. It stores candidate indices in decreasing order of values so weaker jump options can be discarded quickly. This structure ensures efficient lookups for the next optimal jump while processing the array.

What is the time complexity of Maximum Array Hopping Score II?

The optimal monotonic stack solution runs in O(n) time because each index is pushed and popped from the stack at most once. The space complexity is O(n) for storing candidate indices and dynamic scores. A naive dynamic programming solution would take O(n²) time.

Description Hints 2 Solution Video 16:18

3221. Maximum Array Hopping Score II

Medium60.1% acceptance1 companyPremium elsewhere, free here

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.

Example 1:

Input: nums = [1,5,8]

Output: 16

Explanation:

There are two possible ways to reach the last element:

0 -> 1 -> 2 with a score of (1 - 0) * 5 + (2 - 1) * 8 = 13.
0 -> 2 with a score of (2 - 0) * 8 = 16.

Example 2:

Input: nums = [4,5,2,8,9,1,3]

Output: 42

Explanation:

We can do the hopping 0 -> 4 -> 6 with a score of (4 - 0) * 9 + (6 - 4) * 3 = 42.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Zluri

Topics

Hints open one at a time

Hint 1

It’s always optimal to jump to index j with the maximum value.

Hint 2

Keep an array suffixMax and store the maximum of each suffix of the array along with its index.

16:18

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,5,8]

Input

[4,5,2,8,9,1,3]

Your code is saved on this device.Solution