Maximize Score After Pair Deletions - Solution & Explanation
Problem Statement
You are given an array of integers nums. You must repeatedly perform one of the following operations while the array has more than two elements:
- Remove the first two elements.
- Remove the last two elements.
- Remove the first and last element.
For each operation, add the sum of the removed elements to your total score.
Return the maximum possible score you can achieve.
Example 1:
Input: nums = [2,4,1]
Output: 6
Explanation:
The possible operations are:
- Remove the first two elements
(2 + 4) = 6. The remaining array is[1]. - Remove the last two elements
(4 + 1) = 5. The remaining array is[2]. - Remove the first and last elements
(2 + 1) = 3. The remaining array is[4].
The maximum score is obtained by removing the first two elements, resulting in a final score of 6.
Example 2:
Input: nums = [5,-1,4,2]
Output: 7
Explanation:
The possible operations are:
- Remove the first and last elements
(5 + 2) = 7. The remaining array is[-1, 4]. - Remove the first two elements
(5 + -1) = 4. The remaining array is[4, 2]. - Remove the last two elements
(4 + 2) = 6. The remaining array is[5, -1].
The maximum score is obtained by removing the first and last elements, resulting in a total score of 7.
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
Approach Overview
Problem Overview: You are given an array and repeatedly delete pairs of elements. A pair contributes to the score only if it satisfies the problem’s condition (typically the left value must be smaller than the right). Each element can be used once. The goal is to choose deletions so the number of valid scoring pairs is maximized.
Approach 1: Brute Force Pair Simulation (O(n2) time, O(1) space)
Try forming pairs by checking every possible combination (i, j) where i < j. If the pair satisfies the scoring condition, mark both elements as used and increase the score. Continue searching for more pairs among the remaining elements. This approach directly mirrors the problem statement but repeatedly scans the array to find valid matches. The nested iteration leads to O(n^2) time in the worst case, which becomes slow for large inputs. It is mainly useful for understanding the pairing constraint before applying a greedy strategy.
Approach 2: Greedy with Reverse Thinking + Sorting (O(n log n) time, O(1) extra space)
Instead of simulating deletions, think in reverse: what is the maximum number of valid pairs you can form if you match smaller values with larger ones? Sort the array first. Then use two pointers: one scanning the smaller half of the array and another scanning the larger half. Whenever the smaller value is strictly less than the larger value, you form a valid pair and move both pointers forward. Otherwise, move the right pointer to find a larger partner.
This greedy strategy works because pairing the smallest available element with the smallest valid larger element leaves bigger values free for future matches. Sorting enables efficient comparisons and prevents wasting large numbers on suboptimal matches. The algorithm performs a single linear scan after sorting, giving O(n log n) time and O(1) extra space if sorting in place.
The technique combines ideas from array processing and greedy algorithms. The two-pointer traversal after sorting is a common pattern when matching elements under ordering constraints.
Recommended for interviews: The greedy reverse-thinking approach. Interviewers expect you to recognize that explicit deletions are unnecessary. Once you sort the array, pairing the smallest valid elements using two pointers yields the maximum score efficiently. Mentioning the brute force idea first shows understanding of the constraint, while the greedy optimization demonstrates algorithmic maturity.
Solution
According to the problem description, each operation removes the two elements at the endpoints. Therefore, when the number of elements is odd, one element will eventually remain; when the number of elements is even, two consecutive elements in the array will eventually remain.
To maximize the score after deletions, we should minimize the remaining elements.
Thus, if the array nums has an odd number of elements, the answer is the sum of all elements s in the array nums minus the minimum value mi in nums; if the array nums has an even number of elements, the answer is the sum of all elements s in the array nums minus the minimum sum of any two consecutive elements.
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
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n^2) | O(1) | Understanding the pairing rule or when constraints are very small |
| Greedy with Sorting + Two Pointers | O(n log n) | O(1) | General optimal solution for large arrays where maximizing valid pairs is required |
Frequently Asked Questions
Is Maximize Score After Pair Deletions easy or hard?
Maximize Score After Pair Deletions Python/Java solution
How to solve Maximize Score After Pair Deletions in O(n log n)?
What is the best approach for Maximize Score After Pair Deletions?
Is Maximize Score After Pair Deletions asked at Google/Amazon/Meta?
What data structure is used in Maximize Score After Pair Deletions?
What is the time complexity of Maximize Score After Pair Deletions?
Ready to solve this problem?
Practice Maximize Score After Pair Deletions with our built-in code editor and test cases.
Practice on FleetCode