3040. Maximum Number of Operations With the Same Score II
Problem Description
In this problem, we're asked to focus on an array of integers called nums
. We can perform an operation on this array as long as it has at least two elements left. An operation consists of choosing and deleting any two elements from the array based on the following three possibilities:
- The first two elements.
- The last two elements.
- The first and the last elements.
The score for an operation is calculated by summing up the deleted elements. We need to determine the maximum number of operations we can perform where each operation yields the same score. The goal is to return this maximum number of operations that all have the same score.
To understand how to approach this problem, one must recognize the constraint that every operation must yield the same score. This significantly narrows down the possibilities and directs us towards considering only specific pairs that sum up to a uniform score.
Intuition
The solution to this problem involves memorization and depth-first search (DFS) to explore all valid operations. Given the constraint that all operations must yield the same score, the initial observation is that there are only three potential scores, based on pairs that can be taken from either the beginning or the end of the array. These scores are:
- The sum of the first two elements.
- The sum of the last two elements.
- The sum of the first and the last elements.
Using these scores, we use DFS to determine the maximum number of pairs that can be created with the same sum. A recursive dfs
function is employed to attempt to form pairs starting from different indices of the array for each of the three scores. The arguments i
and j
represent the current subarray's bounds we're searching, and s
represents the targeted score. The function returns the maximum number of valid operations between positions i
and j
.
To avoid redundant calculations, we use memorization (caching the results of previous computations). This optimization is particularly useful when overlapping subproblems occur, which is a common characteristic in this kind of recursive search.
In summary, the intuition is to exhaustively search for the maximum number of pairs that can be formed for each of the three possible scores and to use caching to optimize the process. Finally, we compare the results of these three exhaustive searches to find and return the maximum achievable number of operations with the same score.
Learn more about Memoization and Dynamic Programming patterns.
Solution Approach
The solution provided utilizes a recursive DFS (Depth-First Search) strategy, coupled with memoization to significantly reduce the complexity that would typically be associated with brute force recursive algorithms due to repeated computations.
DFS with Memoization
The core algorithm is wrapped within the dfs(i, j, s)
function, where i
and j
represent the indices defining the current subarray of nums
, and s
is the constant score that all operations must match.
Here's a deep dive into the dfs
function steps:
-
Base Case: If the current subarray size defined by
i
andj
is less than 2 (j - i < 1
), we cannot perform any more operations, so we return0
. -
Recursive Step: The function attempts to delete a pair of elements from either end of the current subarray or from both ends, provided the sum of the chosen elements equals
s
. It explores three possibilities:- If
nums[i] + nums[i + 1] == s
, deletes these elements and proceeds recursively withdfs(i + 2, j, s)
. - If
nums[i] + nums[j] == s
, deletes these elements and proceeds recursively withdfs(i + 1, j - 1, s)
. - If
nums[j - 1] + nums[j] == s
, deletes these elements and proceeds recursively withdfs(i, j - 2, s)
.
- If
Each recursive call returns the maximum number of operations starting from that subsequence with indices i
and j
. The function keeps track of the maximum possible operations (ans
) that respect the equal score rule in each subtree, essentially performing a depth-first traversal of all the valid operation sequences.
Memoization:
To avoid recalculating the results for the same subarray, the dfs
function uses the @cache
decorator for memoization, which stores the result of each unique (i, j, s)
state. This optimization prevents duplicate calculations, which can quickly explode in a recursive algorithm.
Main Solution Workflow:
The solution block calculates the maximum possible operations for each of the three valid scores separately. For each score, we adjust the subarray and call the dfs
function:
- The score is the sum of the first two elements:
dfs(2, n - 1, nums[0] + nums[1])
- The score is the sum of the last two elements:
dfs(0, n - 3, nums[-1] + nums[-2])
- The score is the sum of the first and last elements:
dfs(1, n - 2, nums[0] + nums[-1])
The algorithm returns the maximum number of operations for a single score plus one (to account for the initial operation that determined the score).
This approach avoids unnecessary computations while effectively exploring all meaningful paths, leading to an efficient solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example where nums = [5, 3, 1, 2, 4, 6]
. The task is to find the maximum number of operations with equal scores.
According to our problem description, we have three initial scores to consider based on the first two elements, the last two elements, and the first and last elements. These scores are:
nums[0] + nums[1] = 5 + 3 = 8
nums[5] + nums[4] = 6 + 4 = 10
nums[0] + nums[5] = 5 + 6 = 11
Each score will lead to a different path of operations and we have to explore each through DFS.
Let's pick the first score (8
) and apply our DFS approach:
-
Start with
dfs(2, n - 1, nums[0] + nums[1])
which isdfs(2, 5, 8)
. We are looking to find pairs that sum up to8
in the subarraynums[2:6]
which is[1, 2, 4, 6]
. -
For the current subarray, neither the first two
1 + 2
nor the last two4 + 6
sum up to8
, but the first and last1 + 6
do. We can perform one operation here bringing our subarray to[2, 4]
. -
With the new subarray
[2, 4]
, we notice that2 + 4
equals6
, not8
. Hence, we cannot perform any further operations to match our score of8
. Thedfs
function would return0
for this path because we have no more valid operations. -
The result for the first score would then be one initial operation that determined the score, plus
dfs(2, 5, 8)
which returns0
. So, for a score of8
, we get1 + 0 = 1
operation.
Applying the same steps for the second and third scores (10
and 11
respectively), we would eventually find the maximum number of operations for each score and then return the largest among them. This way, we will have recursively explored all possible operations respecting the constraint that they should all yield the same score and guaranteed to have found the maximum number of such operations.
Suppose the second starting score 10
led to the maximum of 2
operations. Then, the result for our nums
array would be 2 + 1 = 3
operations including the operation that yielded the initial score of 10
.
This example simplifies the DFS process but illustrates the recursive nature and decision-making involved in arriving at the solution using the described approach with memoization aiding efficiency.
Solution Implementation
1from functools import lru_cache # Import lru_cache for memoization
2
3class Solution:
4 def maxOperations(self, nums: List[int]) -> int:
5 # Use lru_cache decorator to cache the results of the recursive calls
6 @lru_cache(maxsize=None)
7 def dfs(start: int, end: int, target_sum: int) -> int:
8 # Base case: if the subarray has less than two elements, no pair can be formed
9 if end - start < 1:
10 return 0
11 max_operations = 0
12 # If the first two elements make up the target sum, explore the subproblem excluding them
13 if nums[start] + nums[start + 1] == target_sum:
14 max_operations = max(max_operations, 1 + dfs(start + 2, end, target_sum))
15 # If the first and last elements make up the target sum, explore the subproblem excluding them
16 if nums[start] + nums[end] == target_sum:
17 max_operations = max(max_operations, 1 + dfs(start + 1, end - 1, target_sum))
18 # If the last two elements make up the target sum, explore the subproblem excluding them
19 if nums[end - 1] + nums[end] == target_sum:
20 max_operations = max(max_operations, 1 + dfs(start, end - 2, target_sum))
21 return max_operations
22
23 # Calculate the total length of the array
24 n = len(nums)
25 # Try all possible pairs that include the first and last element
26 max_ops_first_two = dfs(2, n - 1, nums[0] + nums[1])
27 max_ops_last_two = dfs(0, n - 3, nums[-1] + nums[-2])
28 max_ops_first_last = dfs(1, n - 2, nums[0] + nums[-1])
29 # One operation is already counted so we add 1 to the maximum of the three possibilities
30 return 1 + max(max_ops_first_two, max_ops_last_two, max_ops_first_last)
31
1class Solution {
2 private Integer[][] memo;
3 private int[] numbers;
4 private int targetSum;
5 private int arrayLength;
6
7 // Main function to calculate the maximum operations
8 public int maxOperations(int[] nums) {
9 // Initialize class variables with the input
10 this.numbers = nums;
11 arrayLength = nums.length;
12
13 // Calculate sub-results for different array portions and starting points
14 int resultWithFirstTwo = calculateSubResult(2, arrayLength - 1, nums[0] + nums[1]);
15 int resultWithLastTwo = calculateSubResult(0, arrayLength - 3, nums[arrayLength - 2] + nums[arrayLength - 1]);
16 int resultWithFirstAndLast = calculateSubResult(1, arrayLength - 2, nums[0] + nums[arrayLength - 1]);
17
18 // Return 1 plus the maximum of the calculated sub-results
19 return 1 + Math.max(resultWithFirstTwo, Math.max(resultWithLastTwo, resultWithFirstAndLast));
20 }
21
22 // Helper to set up and start the DFS search on sub-arrays
23 private int calculateSubResult(int i, int j, int s) {
24 memo = new Integer[arrayLength][arrayLength]; // Memoization table
25 this.targetSum = s; // The desired sum for a pair
26 return depthFirstSearch(i, j);
27 }
28
29 // Depth First Search to find the maximum operations
30 private int depthFirstSearch(int i, int j) {
31 // Base case: If there is less than 2 elements, no pairs can be formed
32 if (j - i < 1) {
33 return 0;
34 }
35
36 // If we already computed the value for this sub-array, return it
37 if (memo[i][j] != null) {
38 return memo[i][j];
39 }
40
41 int maxOperations = 0;
42
43 // If the first two elements form a pair, proceed to check the remaining elements
44 if (numbers[i] + numbers[i + 1] == targetSum) {
45 maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i + 2, j));
46 }
47
48 // If the first and last elements form a pair, proceed to check the remaining elements
49 if (numbers[i] + numbers[j] == targetSum) {
50 maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i + 1, j - 1));
51 }
52
53 // If the last two elements form a pair, proceed to check the remaining elements
54 if (numbers[j - 1] + numbers[j] == targetSum) {
55 maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i, j - 2));
56 }
57
58 // Save the result in memo table before returning
59 memo[i][j] = maxOperations;
60 return maxOperations;
61 }
62}
63
1#include <vector>
2#include <cstring>
3#include <functional>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int maxOperations(vector<int>& nums) {
11 // Get the size of the nums vector
12 int n = nums.size();
13
14 // Create a memoization table
15 int dp[n][n];
16
17 // Define a lambda function to perform DFS and compute maximum operations
18 auto computeMaxOperations = [&](int start, int end, int targetSum) -> int {
19 // Initialize dp with -1 to indicate unvisited states
20 memset(dp, -1, sizeof(dp));
21
22 // Define the DFS function to find pairs that sum up to targetSum
23 function<int(int, int)> dfs = [&](int left, int right) -> int {
24 // If there are less than two elements, no more pairs can be formed
25 if (right - left < 1) {
26 return 0;
27 }
28
29 // Return already computed value to avoid recomputation
30 if (dp[left][right] != -1) {
31 return dp[left][right];
32 }
33
34 int maxPairs = 0; // Initialize maxPairs to 0
35
36 // Check if the first two numbers form a valid pair and choose the maximum result
37 if (nums[left] + nums[left + 1] == targetSum) {
38 maxPairs = max(maxPairs, 1 + dfs(left + 2, right));
39 }
40
41 // Check if the first and last numbers form a valid pair and choose the maximum result
42 if (nums[left] + nums[right] == targetSum) {
43 maxPairs = max(maxPairs, 1 + dfs(left + 1, right - 1));
44 }
45
46 // Check if the last two numbers form a valid pair and choose the maximum result
47 if (nums[right - 1] + nums[right] == targetSum) {
48 maxPairs = max(maxPairs, 1 + dfs(left, right - 2));
49 }
50
51 // Save and return the result
52 return dp[left][right] = maxPairs;
53 };
54
55 // Execute dfs starting from the given start and end indices
56 return dfs(start, end);
57 };
58
59 // Using the first two numbers in nums, calculate maximum number of operations
60 int option1 = computeMaxOperations(2, n - 1, nums[0] + nums[1]);
61 // Using the last two numbers in nums, calculate maximum number of operations
62 int option2 = computeMaxOperations(0, n - 3, nums[n - 2] + nums[n - 1]);
63 // Using the first and last number in nums, calculate maximum number of operations
64 int option3 = computeMaxOperations(1, n - 2, nums[0] + nums[n - 1]);
65
66 // Return the maximum of the three options plus one (the one used for the calculation)
67 return 1 + max({option1, option2, option3});
68 }
69};
70
1// Define a new memoization array to store the results of subproblems
2let memo: number[][];
3
4// This helper method initializes the memoization array
5function initializeMemo(n: number): void {
6 memo = Array.from({ length: n }, () => Array(n).fill(-1));
7}
8
9// This method computes the maximum number of operations by using a DFS approach
10// with memoization to avoid recomputation of subproblems
11function computeMaxOperations(i: number, j: number, targetSum: number): number {
12 // Base case: if there are less than two elements remaining, cannot form a pair
13 if (j - i < 1) {
14 return 0;
15 }
16 // If the result of the current subproblem is already computed, return it
17 if (memo[i][j] !== -1) {
18 return memo[i][j];
19 }
20 let ans = 0;
21 // Check if the two elements at the start of the range add up to the target sum
22 if (nums[i] + nums[i + 1] === targetSum) {
23 ans = Math.max(ans, 1 + computeMaxOperations(i + 2, j, targetSum));
24 }
25 // Check if the first and last elements in the range add up to the target sum
26 if (nums[i] + nums[j] === targetSum) {
27 ans = Math.max(ans, 1 + computeMaxOperations(i + 1, j - 1, targetSum));
28 }
29 // Check if the two elements at the end of the range add up to the target sum
30 if (nums[j - 1] + nums[j] === targetSum) {
31 ans = Math.max(ans, 1 + computeMaxOperations(i, j - 2, targetSum));
32 }
33 // Memoize and return the maximum number of operations that can be performed
34 memo[i][j] = ans;
35 return ans;
36}
37
38function maxOperations(nums: number[]): number {
39 const n = nums.length;
40 // Initialize the memo array with proper length and filled with -1
41 initializeMemo(n);
42 // Calculate the maximum operations for each of the three possible starting pairs
43 const resultA = computeMaxOperations(2, n - 1, nums[0] + nums[1]);
44 const resultB = computeMaxOperations(0, n - 3, nums[n - 2] + nums[n - 1]);
45 const resultC = computeMaxOperations(1, n - 2, nums[0] + nums[n - 1]);
46 // Return the maximum of the three calculations incremented by one
47 // because we're starting with one operation already made
48 return 1 + Math.max(resultA, resultB, resultC);
49}
50
Time and Space Complexity
The time complexity of the given code is O(n^2)
where n
is the length of the input list nums
. This is because the dfs
function that is used to compute the answer is called recursively, and at each step, it considers either incrementing the left pointer by 2, incrementing the left pointer and decrementing the right pointer, or decrementing the right pointer by 2. Therefore, at most n/2
recursive calls can be made at each level of recursion before base cases are reached, and there are n
possible positions for the left and right pointers, which results in O(n^2)
recursive calls in the worst case.
The space complexity of the code is also O(n^2)
due to the memoization (@cache
) used in the recursive dfs
function. This memoization stores results for each unique pair of indices (i, j) to avoid redundant calculations. Since there can be n
choices for i
and n
choices for j
, there can be at most O(n^2)
unique states to store, which determines the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!