Maximum Number of Operations With the Same Score II Solution
Maximum Number of Operations With the Same Score II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Operations With the Same Score II is a medium coding problem on arrays, dynamic programming and memoization, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Memoization
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
While nums has at least two elements you may perform an operation of one of three kinds:
- delete the first two elements,
- delete the last two elements, or
- delete the first and the last element.
The score of an operation is the sum of the two deleted elements. Perform as many operations as possible such that all of them have the same score, and return that maximum number of operations.
Example 1
Input: nums = [3,2,1,2,3,4]
Output: 3
Explanation: Delete 3 and 2 (score 5), then 1 and 4 (first and last), then 2 and 3.
Example 2
Input: nums = [3,2,6,1,4]
Output: 2
Explanation: Delete 3 and 2 (score 5), then the last two, 1 and 4 (score 5). Only `[6]` is left.
Example 3
Input: nums = [7,7]
Output: 1
Constraints
2 <= nums.length <= 20001 <= nums[i] <= 1000
Hints for Maximum Number of Operations With the Same Score II
Hint 1
The first operation fixes the score, and it can only be one of three sums:
nums[0] + nums[1],nums[n-2] + nums[n-1]ornums[0] + nums[n-1].Hint 2
After any sequence of operations the remaining elements form a contiguous window
nums[l..r].Hint 3
For each of the three scores, run an interval DP over windows:
f(l, r)= most operations onnums[l..r], trying each of the three deletions that match the score.
How to solve Maximum Number of Operations With the Same Score II
Every operation removes from the ends, so the state is the window [l, r] that remains. Fix the score (three candidates) and memoise the best number of operations per window.
Approach
- For each candidate score
Sin{nums[0]+nums[1], nums[n-2]+nums[n-1], nums[0]+nums[n-1]}: - Define
f(l, r) = 0when fewer than two elements remain; otherwise the maximum of1 + f(l+2, r)ifnums[l]+nums[l+1] = S,1 + f(l, r-2)ifnums[r-1]+nums[r] = S, and1 + f(l+1, r-1)ifnums[l]+nums[r] = S. - Fill the table bottom-up by increasing window length (or memoise top-down).
- Return the largest
f(0, n-1)over the three scores.
Why it works
The first operation must be one of the three listed deletions, so the common score is one of three values; for a fixed score, every legal continuation from window [l, r] is one of the three moves, and each leads to a smaller window solved optimally by the DP.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Trying every possible score instead of the three candidates multiplies the work for nothing.
- The window shrinks by two each time — windows of length 0 and 1 are the base cases.
- A greedy that always deletes the first matching pair can miss longer sequences.
Reference solution
Python
from typing import List
def maxOperations(nums: List[int]) -> int:
n = len(nums)
def solve(score):
# h[l][r] = most operations on the window nums[l:r]
h = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length
best = 0
if nums[l] + nums[l + 1] == score:
best = 1 + h[l + 2][r]
if nums[r - 2] + nums[r - 1] == score and 1 + h[l][r - 2] > best:
best = 1 + h[l][r - 2]
if nums[l] + nums[r - 1] == score and 1 + h[l + 1][r - 1] > best:
best = 1 + h[l + 1][r - 1]
h[l][r] = best
return h[0][n]
return max(solve(nums[0] + nums[1]), solve(nums[-2] + nums[-1]), solve(nums[0] + nums[-1]))Java
static int sameScoreSolve(int[] nums, int score) {
int n = nums.length;
int[][] h = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len <= n; l++) {
int r = l + len;
int best = 0;
if (nums[l] + nums[l + 1] == score) best = 1 + h[l + 2][r];
if (nums[r - 2] + nums[r - 1] == score) best = Math.max(best, 1 + h[l][r - 2]);
if (nums[l] + nums[r - 1] == score) best = Math.max(best, 1 + h[l + 1][r - 1]);
h[l][r] = best;
}
}
return h[0][n];
}
public static int maxOperations(int[] nums) {
int n = nums.length;
int a = sameScoreSolve(nums, nums[0] + nums[1]);
int b = sameScoreSolve(nums, nums[n - 2] + nums[n - 1]);
int c = sameScoreSolve(nums, nums[0] + nums[n - 1]);
return Math.max(a, Math.max(b, c));
}C++
int sameScoreSolve(const vector<int>& nums, int score) {
int n = nums.size();
vector<vector<int>> h(n + 1, vector<int>(n + 1, 0));
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len <= n; l++) {
int r = l + len;
int best = 0;
if (nums[l] + nums[l + 1] == score) best = 1 + h[l + 2][r];
if (nums[r - 2] + nums[r - 1] == score) best = max(best, 1 + h[l][r - 2]);
if (nums[l] + nums[r - 1] == score) best = max(best, 1 + h[l + 1][r - 1]);
h[l][r] = best;
}
}
return h[0][n];
}
int maxOperations(vector<int>& nums) {
int n = nums.size();
int a = sameScoreSolve(nums, nums[0] + nums[1]);
int b = sameScoreSolve(nums, nums[n - 2] + nums[n - 1]);
int c = sameScoreSolve(nums, nums[0] + nums[n - 1]);
return max(a, max(b, c));
}JavaScript
var maxOperations = function(nums) {
var n = nums.length;
var solve = function(score) {
var h = [];
for (var i = 0; i <= n; i++) h.push(new Array(n + 1).fill(0));
for (var len = 2; len <= n; len++) {
for (var l = 0; l + len <= n; l++) {
var r = l + len;
var best = 0;
if (nums[l] + nums[l + 1] === score) best = 1 + h[l + 2][r];
if (nums[r - 2] + nums[r - 1] === score && 1 + h[l][r - 2] > best) best = 1 + h[l][r - 2];
if (nums[l] + nums[r - 1] === score && 1 + h[l + 1][r - 1] > best) best = 1 + h[l + 1][r - 1];
h[l][r] = best;
}
}
return h[0][n];
};
return Math.max(solve(nums[0] + nums[1]), solve(nums[n - 2] + nums[n - 1]), solve(nums[0] + nums[n - 1]));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming