Maximum Number of Operations With the Same Score II solution and explanation
9 more videos on this problem
3040. Maximum Number of Operations With the Same Score II | Standard DP✅Aryan Mittal · 16:55 · 2K views
Maximum Number of Operations With the Same Score II - Python - Leetcode 3040CheatCode Ninja · 11:01 · 685 views
3040. Maximum Number of Operations With the Same Score II (Leetcode Medium)Programming Live with Larry · 9:19 · 425 views
3040. Maximum Number of Operations With the Same Score II | Leetcode Biweekly 124codingMohan · 37:00 · 422 views
3040. Maximum Number of Operations With the Same Score II | DP 🔥 | LeetCode Biweekly Contest | C++Priyanshi Porwal · 15:50 · 194 views
LeetCode 3040 - Maximum Number of Operations With he Same Score II - PythonAlpha-Code · 10:01 · 71 views
Leetcode 3040. Maximum Number of Operations With the Same Score || || Leetcode Biweekly Contest 124Geekstocode · 9:08 · 68 views
3040 Maximum Number of Operations With the Same Score II LeetCode Biweekly Contest 124 || DPFORT of BELLMAN · 26:21 · 34 views
Maximum Number of Operations With the Same Score II Biweekly Contest | Python | HarshCodeHarshCode · 14:11 · 22 views
Maximum Number of operation with the same score II | LeetcodeCoding Arena · 2:34 · 2 views
The problem
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.
def max_operations(nums):
left, right = 0, len(nums) - 1
left_sum, right_sum, max_ops = 0, 0, 0
while left < right:
if left_sum < right_sum:
left_sum += nums[left]
left += 1
elif left_sum > right_sum:
right_sum += nums[right]
right -= 1
else:
max_ops += 1
left_sum += nums[left]
right_sum += nums[right]
left += 1
right -= 1
return max_ops
nums = [3,2,1,2,3,4]
operations = max_operations(nums)
print("Maximum operations:", operations)public class MaxOperations {
public int maxOperations(int[] nums) {
int left = 0, right = nums.length - 1;
int leftSum = 0, rightSum = 0, maxOps = 0;
while (left < right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else if (leftSum > rightSum) {
rightSum += nums[right--];
} else {
maxOps++;
leftSum += nums[left++];
rightSum += nums[right--];
}
}
return maxOps;
}
public static void main(String[] args) {
MaxOperations mo = new MaxOperations();
int[] nums = {3,2,1,2,3,4};
int operations = mo.maxOperations(nums);
System.out.println("Maximum operations: " + operations);
}
}#include <iostream>
#include <vector>
int maxOperations(std::vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int leftSum = 0, rightSum = 0, maxOps = 0;
while (left < right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else if (leftSum > rightSum) {
rightSum += nums[right--];
} else {
maxOps++;
leftSum += nums[left++];
rightSum += nums[right--];
}
}
return maxOps;
}
int main() {
std::vector<int> nums = {3,2,1,2,3,4};
int operations = maxOperations(nums);
std::cout << "Maximum operations: " << operations << std::endl;
return 0;
}function maxOperations(nums) {
let left = 0, right = nums.length - 1;
let leftSum = 0, rightSum = 0, maxOps = 0;
while (left < right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else if (leftSum > rightSum) {
rightSum += nums[right--];
} else {
maxOps++;
leftSum += nums[left++];
rightSum += nums[right--];
}
}
return maxOps;
}
const nums = [3,2,1,2,3,4];
console.log("Maximum operations:", maxOperations(nums));#include <stdio.h>
int maxOperations(int* nums, int numsSize) {
int left = 0, right = numsSize - 1;
int leftSum = 0, rightSum = 0, maxOps = 0;
while (left < right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else if (leftSum > rightSum) {
rightSum += nums[right--];
} else {
maxOps++;
leftSum += nums[left++];
rightSum += nums[right--];
}
}
return maxOps;
}
int main() {
int nums[] = {3,2,1,2,3,4};
int operations = maxOperations(nums, 6);
printf("Maximum operations: %d\n", operations);
return 0;
}using System;
public class MaxOperations {
public int MaxOperations(int[] nums) {
int left = 0, right = nums.Length - 1;
int leftSum = 0, rightSum = 0, maxOps = 0;
while (left < right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else if (leftSum > rightSum) {
rightSum += nums[right--];
} else {
maxOps++;
leftSum += nums[left++];
rightSum += nums[right--];
}
}
return maxOps;
}
public static void Main() {
MaxOperations mo = new MaxOperations();
int[] nums = {3,2,1,2,3,4};
int operations = mo.MaxOperations(nums);
Console.WriteLine("Maximum operations: " + operations);
}
}In Python, this straightforward algorithm utilizes two pointers and accumulates sums while comparing them to ensure operations that yield the same score.
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.
def max_operations(nums):
sum_frequencies = {}
current_sum = 0
max_operations = 0
for num in nums:
current_sum += num
if current_sum in sum_frequencies:
max_operations = max(max_operations, sum_frequencies[current_sum])
sum_frequencies[current_sum] = sum_frequencies.get(current_sum, 0) + 1
return max_operations
nums = [3,2,1,2,3,4]
operations = max_operations(nums)
print("Maximum operations:", operations)import java.util.HashMap;
public class MaxOperations {
public int maxOperations(int[] nums) {
HashMap<Integer, Integer> sumFrequencies = new HashMap<>();
int sum = 0, maxLength = 0;
for (int num : nums) {
sum += num;
if (sumFrequencies.containsKey(sum)) {
maxLength = Math.max(maxLength, sumFrequencies.get(sum));
}
sumFrequencies.put(sum, sumFrequencies.getOrDefault(sum, 0) + 1);
}
return maxLength;
}
public static void main(String[] args) {
MaxOperations mo = new MaxOperations();
int[] nums = {3,2,1,2,3,4};
int operations = mo.maxOperations(nums);
System.out.println("Maximum operations: " + operations);
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int maxOperations(std::vector<int>& nums) {
std::unordered_map<int, int> sum_freq;
int sum = 0, max_length = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (i > 0 && sum_freq[sum] > 0) {
max_length = std::max(max_length, sum_freq[sum]);
}
++sum_freq[sum];
}
return max_length;
}
int main() {
std::vector<int> nums = {3,2,1,2,3,4};
int operations = maxOperations(nums);
std::cout << "Maximum operations: " << operations << std::endl;
return 0;
}function maxOperations(nums) {
let sumFreq = {};
let currentSum = 0;
let maxOperations = 0;
for (let num of nums) {
currentSum += num;
if (sumFreq.hasOwnProperty(currentSum)) {
maxOperations = Math.max(maxOperations, sumFreq[currentSum]);
}
sumFreq[currentSum] = (sumFreq[currentSum] || 0) + 1;
}
return maxOperations;
}
const nums = [3,2,1,2,3,4];
console.log("Maximum operations:", maxOperations(nums));#include <stdlib.h>
#include <string.h>
int maxOperations(int* nums, int numsSize) {
int sum_frequencies[2001] = {0};
int max_operations = 0;
int sum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += nums[i];
if (i > 0 && sum_frequencies[sum] > 0) {
int max_length = sum_frequencies[sum];
max_operations = max_operations > max_length ? max_operations : max_length;
}
sum_frequencies[sum] += 1;
}
return max_operations;
}
int main() {
int nums[] = {3,2,1,2,3,4};
int operations = maxOperations(nums, 6);
printf("Maximum operations: %d\n", operations);
return 0;
}using System;
using System.Collections.Generic;
public class MaxOperations {
public int MaxOperations(int[] nums) {
Dictionary<int, int> sumFrequencies = new Dictionary<int, int>();
int sum = 0, maxLength = 0;
foreach (int num in nums) {
sum += num;
if (sumFrequencies.ContainsKey(sum)) {
maxLength = Math.Max(maxLength, sumFrequencies[sum]);
}
if (!sumFrequencies.ContainsKey(sum)) {
sumFrequencies[sum] = 0;
}
sumFrequencies[sum]++;
}
return maxLength;
}
public static void Main() {
MaxOperations mo = new MaxOperations();
int[] nums = {3,2,1,2,3,4};
int operations = mo.MaxOperations(nums);
Console.WriteLine("Maximum operations: " + operations);
}
}Utilizing the Python hash map to track the frequency of cumulative sums, this method keeps updating the maximal operation count facilitated by consistent scoring.
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.
function maxOperations(nums: number[]): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(n));
const g = (i: number, j: number, s: number): number => {
f.forEach(row => row.fill(-1));
const dfs = (i: number, j: number): number => {
if (j - i < 1) {
return 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
let ans = 0;
if (nums[i] + nums[i + 1] === s) {
ans = Math.max(ans, 1 + dfs(i + 2, j));
}
if (nums[i] + nums[j] === s) {
ans = Math.max(ans, 1 + dfs(i + 1, j - 1));
}
if (nums[j - 1] + nums[j] === s) {
ans = Math.max(ans, 1 + dfs(i, j - 2));
}
return (f[i][j] = ans);
};
return dfs(i, j);
};
const a = g(2, n - 1, nums[0] + nums[1]);
const b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
const c = g(1, n - 2, nums[0] + nums[n - 1]);
return 1 + Math.max(a, b, c);
}func maxOperations(nums []int) int {
n := len(nums)
var g func(i, j, s int) int
g = func(i, j, s int) int {
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if j-i < 1 {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := 0
if nums[i]+nums[i+1] == s {
ans = max(ans, 1+dfs(i+2, j))
}
if nums[i]+nums[j] == s {
ans = max(ans, 1+dfs(i+1, j-1))
}
if nums[j-1]+nums[j] == s {
ans = max(ans, 1+dfs(i, j-2))
}
f[i][j] = ans
return ans
}
return dfs(i, j)
}
a := g(2, n-1, nums[0]+nums[1])
b := g(0, n-3, nums[n-1]+nums[n-2])
c := g(1, n-2, nums[0]+nums[n-1])
return 1 + max(a, b, c)
}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 | – |
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 |
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 is rated Medium difficulty. The challenge comes from recognizing that the first operation determines the target score and that the remaining problem becomes a dynamic programming search over array ranges.
Maximum Number of Operations With the Same Score II Python/Java solution
Python and Java implementations typically use recursion with memoization or a DP cache keyed by (left, right). The algorithm checks three possible pair removals for each step and stores computed results to maintain O(n^2) time complexity.
How to solve Maximum Number of Operations With the Same Score II in O(n)?
An O(n) solution is not generally possible because the algorithm must explore many subarray states created by removing elements from both ends. The best known solution uses dynamic programming with memoization, resulting in O(n^2) time complexity.
What is the best approach for Maximum Number of Operations With the Same Score II?
The best approach uses a two-pointer recursive strategy with memoization. You treat the array as a range [l, r] and attempt three valid pair removals while maintaining a fixed score determined by the first operation. Caching results for each (l, r) subarray avoids repeated computation, giving O(n^2) time complexity.
Is Maximum Number of Operations With the Same Score II asked at Google/Amazon/Meta?
Problems combining two-pointers and dynamic programming appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that involve removing elements from array ends and optimizing operations are common interview patterns.
What data structure is used in Maximum Number of Operations With the Same Score II?
The core data structure is the array itself, combined with a memoization table or hash map for dynamic programming. Two pointers track the current subarray boundaries while recursion or DP evaluates valid pair removals.
What is the time complexity of Maximum Number of Operations With the Same Score II?
The optimal solution runs in O(n^2) time because each subarray range (l, r) is evaluated at most once with memoization. Space complexity is also O(n^2) due to the DP cache storing results for subproblems.