Maximum Array Hopping Score II solution and explanation
4 more videos on this problem
Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize ScorePrakhar Agrawal · 16:18 · 1K views
Weekly Contest 299 | Leetcode 2321 Maximum Score Of Spliced Array | DP | Kadane algorithmCoding Decoded · 14:14 · 1K views
2321. Maximum Score Of Spliced Array (Leetcode Hard)Programming Live with Larry · 9:49 · 741 views
Leetcode - Maximum Score of Spliced ArrayCoding For Dummies · 9:50 · 66 views
LeetCode 2321 Maximum Score of Spliced Array[CE] Code Engineering · 27:23 · 19 views
The problem
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 -> 2with a score of(1 - 0) * 5 + (2 - 1) * 8 = 13.0 -> 2with 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 <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: You start at index 0 in an array and can jump to any later index j > i. A jump from i to j adds (j - i) * nums[i] to your score. The goal is to reach the last index while maximizing the total score. The challenge is choosing jump boundaries that maximize the contribution from each position.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
The most direct idea is dynamic programming. Let dp[i] represent the maximum score obtainable starting from index i. For each index, iterate over every possible next position j > i and compute (j - i) * nums[i] + dp[j]. Take the maximum of all choices. This approach is straightforward and clearly models the problem, but the nested iteration leads to O(n²) time complexity, which becomes too slow for large inputs.
Approach 2: Greedy + Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a greedy observation with a monotonic stack. If a future index has a larger or equal value, it is usually better to jump there because the multiplier nums[i] stays fixed while the distance grows. Instead of checking every possible destination, maintain a decreasing stack of indices while scanning from right to left. The stack keeps candidate positions that yield better long-term scores.
For each index i, pop smaller values from the stack since they will never produce a better continuation than a larger future value. The next index remaining on the stack becomes the optimal next hop. The score contribution is computed using (next - i) * nums[i] plus the stored result from that position. This reduces repeated comparisons and guarantees each index is pushed and popped at most once.
The technique combines ideas from array traversal, stack processing, and greedy selection. Because every element enters and leaves the stack once, the total complexity becomes O(n) time with O(n) auxiliary space.
Recommended for interviews: Start by explaining the O(n²) dynamic programming formulation to show you understand the scoring transition. Then optimize using a greedy insight with a monotonic stack. Interviewers typically expect the linear solution because it demonstrates pattern recognition with monotonic structures and the ability to eliminate redundant comparisons.
Solution
We observe that for the current position i, we should jump to the next position j with the maximum value to obtain the maximum score.
Therefore, we traverse the array nums, maintaining a stack stk that is monotonically decreasing from the bottom to the top of the stack. For the current position i being traversed, if the value corresponding to the top element of the stack is less than or equal to nums[i], we continuously pop the top element of the stack until the stack is empty or the value corresponding to the top element of the stack is greater than nums[i], and then push i into the stack.
Next, we initialize the answer ans and the current position i = 0, traverse the elements in the stack, each time taking out the top element j, updating the answer ans += nums[j] times (j - i), and then updating i = j.
class Solution:
def maxScore(self, nums: List[int]) -> int:
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] <= x:
stk.pop()
stk.append(i)
ans = i = 0
for j in stk:
ans += nums[j] * (j - i)
i = j
return ansclass Solution {
public long maxScore(int[] nums) {
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < nums.length; ++i) {
while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
stk.pop();
}
stk.push(i);
}
long ans = 0, i = 0;
while (!stk.isEmpty()) {
int j = stk.pollLast();
ans += (j - i) * nums[j];
i = j;
}
return ans;
}
}class Solution {
public:
long long maxScore(vector<int>& nums) {
vector<int> stk;
for (int i = 0; i < nums.size(); ++i) {
while (stk.size() && nums[stk.back()] <= nums[i]) {
stk.pop_back();
}
stk.push_back(i);
}
long long ans = 0, i = 0;
for (int j : stk) {
ans += (j - i) * nums[j];
i = j;
}
return ans;
}
};function maxScore(nums: number[]): number {
const stk: number[] = [];
for (let i = 0; i < nums.length; ++i) {
while (stk.length && nums[stk.at(-1)!] <= nums[i]) {
stk.pop();
}
stk.push(i);
}
let ans = 0;
let i = 0;
for (const j of stk) {
ans += (j - i) * nums[j];
i = j;
}
return ans;
}func maxScore(nums []int) (ans int64) {
stk := []int{}
for i, x := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
i := 0
for _, j := range stk {
ans += int64((j - i) * nums[j])
i = j
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Jump Enumeration | O(n²) | O(1) | Useful for understanding the scoring rule and verifying small inputs |
| Dynamic Programming | O(n²) | O(n) | Clear state transition; good starting point before optimization |
| Greedy + Monotonic Stack | O(n) | O(n) | Optimal solution for large arrays; removes redundant jump checks |
Frequently asked questions
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.