Reach End of Array With Max Score - Solution & Explanation
Problem Statement
You are given an integer array nums of length n.
Your goal is to start at index 0 and reach index n - 1. You can only jump to indices greater than your current index.
The score for a jump from index i to index j is calculated as (j - i) * nums[i].
Return the maximum possible total score by the time you reach the last index.
Example 1:
Input: nums = [1,3,1,5]
Output: 7
Explanation:
First, jump to index 1 and then jump to the last index. The final score is 1 * 1 + 2 * 3 = 7.
Example 2:
Input: nums = [4,3,1,3,2]
Output: 16
Explanation:
Jump directly to the last index. The final score is 4 * 4 = 16.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Approach Overview
Problem Overview: You start at index 0 of an array and want to reach the last index. From index i you can jump to any j > i, gaining score based on the value at nums[i] and the distance traveled. The goal is to choose jumps that maximize the total score by the time you reach the end.
Approach 1: Dynamic Programming with Priority Queue (O(n log n) time, O(n) space)
This method treats the problem as a DP transition. Let dp[i] represent the best score achievable when reaching index i. For each new index, you consider previous indices and compute the best transition using a priority queue that keeps candidates ordered by their contribution to future jumps. Each step pushes potential transitions and removes weaker ones as you move forward. This works well conceptually but adds log n overhead due to heap operations.
Approach 2: Dynamic Programming with Maximum Score Tracking (O(n) time, O(n) space)
The key observation is that every transition depends on the best prior value that can contribute to the next position. Instead of evaluating all previous indices, track the best candidate while scanning from left to right. Maintain the maximum achievable contribution so far and update dp[i] using that value. This eliminates repeated comparisons and reduces the complexity to linear time.
Approach 3: Greedy Approach with Optimization (O(n) time, O(1) space)
A deeper observation simplifies the DP even further. While moving across the array, the optimal move at each step always depends on the maximum nums[i] encountered so far. Keep a running maximum and add it to the total score as you advance one index at a time. Conceptually, this simulates extending the best previous jump across the next position. The greedy approach removes the DP array entirely and runs in constant space. This technique appears often in greedy problems on arrays.
Approach 4: Optimized DP with Monotonic Deque (O(n) time, O(n) space)
A monotonic deque can maintain candidate indices whose contributions remain competitive for future transitions. As you iterate through the array, remove indices that produce worse scores than the current one and push the new index while maintaining order. The front of the deque always provides the best transition for the current position. This pattern is common in optimized dynamic programming problems where previous states dominate others.
Recommended for interviews: The greedy O(n) approach is typically what interviewers expect after discussing the DP formulation. Showing the DP reasoning demonstrates understanding of the state transition, while recognizing the prefix maximum optimization proves you can simplify the solution to linear time and constant space.
Approach 1: Dynamic Programming with Priority Queue
This approach leverages a dynamic programming array to store the best score for each index. To efficiently determine the best possible jump, a priority queue (or max-heap) is used, ensuring that we always jump to the index that provides the highest score increment.
The Python solution initializes a dp array for the best score tracking and a max-heap for jump decisions. For each index, it updates its score based on the most beneficial jump (extracted from the heap) and calculates the score increment. The heap helps maintain efficient access to the largest scores available for valid jumps.
Code
Python
Complexity
Time Complexity: O(n log n) - due to heap operations.
Space Complexity: O(n) - because of the dp array and the heap.
Approach 2: Greedy Approach with Optimization
This method uses a greedy algorithm that inspects potential jumps and immediately selects the one providing the greatest increase in score, factoring directly into the index. This is optimized further by storing interim results from previous jumps.
In this Java implementation, a PriorityQueue is used to efficiently manage possible scores. Each element in the heap is an array storing the score and the position index. The algorithm continuously updates with the best score by popping elements and processing them for valid jumps.
Code
Java
Complexity
Time Complexity: O(n log n) - due to PriorityQueue operations.
Space Complexity: O(n) - for maintaining the dp table and the heap.
Approach 3: Dynamic Programming with Maximum Score Tracking
The idea is to use dynamic programming (DP) to compute and track the maximum score at each index, where the main objective is to utilize past computed results to decide on the best jump strategy. We maintain a DP array where each entry dp[i] stores the maximum possible score to reach index i. We iterate through each index and for every possible jump from i to j (where j > i), update dp[j] with the score from i if it increases the current stored value.
This solution uses dynamic programming to store the best scores for each index i in the array dp. We update each possible jump j from i using the formula (j - i) * nums[i], which calculates the score for jumping from i to j. This brute-force solution demonstrates the DP approach but needs optimization.
Complexity
The time complexity of this solution is O(n^2), which may be inefficient for large n. The space complexity is O(n) due to the storage of the DP array.
Approach 4: Optimized DP with Monotonic Deque
This approach refines the DP solution by using a monotonic queue (or deque) data structure to keep track of indices in such a way that the potential jump computations are efficiently managed. The queue acts as a helper to maintain a list of 'alive' indices that are still valid choices for future jumps based on past score calculations. This optimization alleviates redundant comparisons and updates, significantly reducing the time complexity.
The solution crafts an efficient data structure using a deque to help track the best possible index jumps. This helps to maintain only the relevant indices in the queue. The use of a monotonic queue decreases unnecessary updates, thus, optimizing both time and space usage.
Code
JavaScript
Java
C#
Complexity
The time complexity is O(n) because each element gets pushed and popped from the deque once. The space complexity remains O(n) due to the DP and deque storage.
Approach 5: Greedy
Suppose we jump from index i to index j, then the score is (j - i) times nums[i]. This is equivalent to taking j - i steps, and each step earns a score of nums[i]. Then we continue to jump from j to the next index k, and the score is (k - j) times nums[j], and so on. If nums[i] \gt nums[j], then we should not jump from i to j, because the score obtained this way is definitely less than the score obtained by jumping directly from i to k. Therefore, each time we should jump to the next index with a value greater than the current index.
We can maintain a variable mx to represent the maximum value of nums[i] encountered so far. Then we traverse the array from left to right until the second-to-last element, updating mx each time and accumulating the score.
After the traversal, the result is the maximum total score.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Priority Queue | Time Complexity: O(n log n) - due to heap operations. |
| Greedy Approach with Optimization | Time Complexity: O(n log n) - due to PriorityQueue operations. |
| Dynamic Programming with Maximum Score Tracking | The time complexity of this solution is |
| Optimized DP with Monotonic Deque | The time complexity is |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP with Priority Queue | O(n log n) | O(n) | When implementing a straightforward DP transition and optimizing candidate selection with a heap |
| DP with Maximum Score Tracking | O(n) | O(n) | General DP solution that removes the heap but still keeps an explicit DP array |
| Greedy Optimization | O(n) | O(1) | Best practical solution when the optimal contribution comes from the maximum prefix value |
| DP with Monotonic Deque | O(n) | O(n) | Useful when maintaining a set of dominant previous states for future transitions |
Video Solution
Reach End of Array With Max Score || LeetCode Weekly Contest 414 || Leetcode Solution • codi • 1,384 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reach End of Array With Max Score easy or hard?
Reach End of Array With Max Score Python/Java solution
How to solve Reach End of Array With Max Score in O(n)?
What is the best approach for Reach End of Array With Max Score?
Is Reach End of Array With Max Score asked at Google/Amazon/Meta?
What data structure is used in Reach End of Array With Max Score?
What is the time complexity of Reach End of Array With Max Score?
Ready to solve this problem?
Practice Reach End of Array With Max Score with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor