Maximum Number of Operations With the Same Score II - Solution & Explanation
Problem Statement
Given an array of integers called nums, you can perform any of the following operation while nums contains at least 2 elements:
- Choose the first two elements of
numsand delete them. - Choose the last two elements of
numsand delete them. - Choose the first and the last elements of
numsand delete them.
The score of the operation is the sum of the deleted elements.
Your task is to find the maximum number of operations that can be performed, such that all operations have the same score.
Return the maximum number of operations possible that satisfy the condition mentioned above.
Example 1:
Input: nums = [3,2,1,2,3,4] Output: 3 Explanation: We perform the following operations: - Delete the first two elements, with score 3 + 2 = 5, nums = [1,2,3,4]. - Delete the first and the last elements, with score 1 + 4 = 5, nums = [2,3]. - Delete the first and the last elements, with score 2 + 3 = 5, nums = []. We are unable to perform any more operations as nums is empty.
Example 2:
Input: nums = [3,2,6,1,4] Output: 2 Explanation: We perform the following operations: - Delete the first two elements, with score 3 + 2 = 5, nums = [6,1,4]. - Delete the last two elements, with score 1 + 4 = 5, nums = [6]. It can be proven that we can perform at most 2 operations.
Constraints:
2 <= nums.length <= 20001 <= nums[i] <= 1000
Approach Overview
Problem Overview: You are given an integer array. Each operation removes two numbers from either the beginning or end of the array, and the sum of those two numbers becomes the operation's score. Every operation must produce the same score. The task is to maximize the number of operations you can perform.
The first operation determines the required score. After that, every pair you remove must match this sum. Because elements can only be removed from the edges, the problem naturally becomes a range decision problem over the array.
Approach 1: Two-Pointer Technique + Memoization (O(n2) time, O(n2) space)
The optimal strategy is to simulate removing elements from both ends using a two-pointer state (left, right). The first operation can produce three possible scores: nums[0] + nums[1], nums[n-2] + nums[n-1], or nums[0] + nums[n-1]. Once the target score is fixed, recursively attempt valid operations that maintain the same score. From a state (l, r), you check three options: remove the first two elements, remove the last two elements, or remove one from each side. If the pair matches the target score, move the pointers accordingly and continue.
Without caching, many subranges repeat. Using memoization or a DP table keyed by (l, r) avoids recomputation and guarantees each subproblem is solved once. This leads to O(n2) time and O(n2) space. The method relies heavily on the two-pointer technique combined with recursive decision making over the array.
Approach 2: Sliding Window + Hash Map Exploration (O(n2) time, O(n) space)
Another way to reason about the problem is to treat each possible first score as a candidate and simulate shrinking the array while maintaining that score. For a chosen score, maintain pointers at both ends and greedily test whether any of the three valid pair choices matches the score. A small hash map or counter can track previously evaluated ranges to avoid redundant work.
This approach still explores many overlapping intervals but uses lightweight bookkeeping instead of a full DP matrix. It works well for medium constraints where the recursion depth is manageable. Time complexity remains O(n2) in the worst case, while space drops closer to O(n) for tracking visited states and recursion.
Recommended for interviews: The two-pointer recursion with memoization is the expected solution. It clearly models the subproblem max operations in subarray [l, r] while enforcing a fixed score. Starting with all three possible initial scores shows you understand the constraints, and adding memoization demonstrates strong dynamic programming skills.
Approach 1: Two-Pointer Technique
This approach involves using two pointers to simulate deletions and track sums to ensure operations result in the same score. Start with a sum from both ends and adjust the pointers based on the score requirement.
This C solution uses two pointers, left and right, along with two sum trackers (leftSum and rightSum) to maintain sums of considered subarrays. When both sums align, an equal score operation is counted, and pointers are adjusted for further operations.
Complexity
Time Complexity: O(n), Space Complexity: O(1)
Approach 2: Sliding Window + Hash Map
This approach constructs sliding windows using hash maps to track frequency of sums. The goal is to identify the largest frequency of a particular sum, ensuring maximum operations with uniform scores.
In C, this solution uses a rudimentary hash table to track aid frequencies of cumulative sums to ensure operations have matching scores.
Complexity
Time Complexity: O(n^2), Space Complexity: O(n)
Approach 3: Memorization Search
There are three possible values for the score s, which are s = nums[0] + nums[1], s = nums[0] + nums[n-1], and s = nums[n-1] + nums[n-2]. We can perform memorization search for these three cases separately.
We design a function dfs(i, j), which represents the maximum number of operations from index i to index j when the score is s. The execution process of function dfs(i, j) is as follows:
- If
j - i < 1, it means that the length of the interval[i, j]is less than2, and no operation can be performed, so return0. - If
nums[i] + nums[i+1] = s, it means that the elements at indexiand indexi+1can be deleted. In this case, the maximum number of operations is1 + dfs(i+2, j). - If
nums[i] + nums[j] = s, it means that the elements at indexiand indexjcan be deleted. In this case, the maximum number of operations is1 + dfs(i+1, j-1). - If
nums[j-1] + nums[j] = s, it means that the elements at indexj-1and indexjcan be deleted. In this case, the maximum number of operations is1 + dfs(i, j-2). - Return the maximum of the above values.
Finally, we calculate the maximum number of operations for the three cases separately, and return the maximum value.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), Space Complexity: O(1) |
| Sliding Window + Hash Map | Time Complexity: O(n^2), Space Complexity: O(n) |
| Memorization Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer + Memoization | O(n^2) | O(n^2) | Best general solution when exploring subarray states with repeated overlap |
| Sliding Window + Hash Map Exploration | O(n^2) | O(n) | Useful when simulating shrinking ranges with lighter memory usage |
Video Solution
3040. Maximum Number of Operations With the Same Score II | Standard DP✅ • Aryan Mittal • 2,183 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Operations With the Same Score II easy or hard?
Maximum Number of Operations With the Same Score II Python/Java solution
How to solve Maximum Number of Operations With the Same Score II in O(n)?
What is the best approach for Maximum Number of Operations With the Same Score II?
Is Maximum Number of Operations With the Same Score II asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Operations With the Same Score II?
What is the time complexity of Maximum Number of Operations With the Same Score II?
Ready to solve this problem?
Practice Maximum Number of Operations With the Same Score II with our built-in code editor and test cases.
Practice on FleetCode