Scale Engineer

Maximum Number of Operations With the Same Score II

Med
#2708Time: O(3^(n/2)) - In the worst-case scenario, each recursive call can branch into three further calls. The depth of the recursion is roughly `n/2`. This leads to an exponential number of function calls, making it too slow for the given constraints.Space: O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be up to `n/2` in the worst case.
Patterns
Dynamic ProgrammingMemoization
Data structures
Array

Prompt

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 nums and delete them.
  • Choose the last two elements of nums and delete them.
  • Choose the first and the last elements of nums and 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 <= 2000
  • 1 <= nums[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's recursive nature into code. We identify that the first operation determines the target score for all subsequent operations. There are three possible first moves, leading to three potential target scores. For each target score, we can define a recursive function that explores all possible sequences of operations. The state of the recursion can be defined by the start and end indices of the current subarray. The function tries all three types of operations (from the front, from the back, from both ends) and recursively calls itself on the smaller subarray, taking the path that yields the maximum number of operations.

Algorithm

  • The problem can be broken down into three main scenarios based on the first operation: a. Removing the first two elements (nums[0], nums[1]) b. Removing the last two elements (nums[n-1], nums[n-2]) c. Removing the first and last elements (nums[0], nums[n-1])
  • The sum of the elements removed in the first operation becomes the target score for all subsequent operations.
  • We define a recursive helper function, say solve(start, end, score), which calculates the maximum number of operations for the subarray nums[start...end] with the given score.
  • Inside solve(start, end, score):
    • Base Case: If start >= end (less than two elements left), return 0.
    • Recursive Step: Explore three possible moves:
      • If nums[start] + nums[start+1] == score, recursively call 1 + solve(start+2, end, score).
      • If nums[end] + nums[end-1] == score, recursively call 1 + solve(start, end-2, score).
      • If nums[start] + nums[end] == score, recursively call 1 + solve(start+1, end-1, score).
  • The result for the current state is the maximum of the outcomes of the valid moves. If no move is valid, return 0.
  • The final answer is the maximum result obtained from the three initial scenarios.

Walkthrough

The main function maxOperations considers three initial scenarios:

  1. Removing nums[0] and nums[1]. The score is nums[0] + nums[1]. We get 1 operation plus whatever we can get from the rest of the array nums[2...n-1].
  2. Removing nums[n-2] and nums[n-1]. The score is nums[n-2] + nums[n-1]. We get 1 operation plus the result from nums[0...n-3].
  3. Removing nums[0] and nums[n-1]. The score is nums[0] + nums[n-1]. We get 1 operation plus the result from nums[1...n-2].

A helper function solve(nums, start, end, score) is implemented to handle the recursive calculation. It returns the maximum number of operations possible on the subarray nums[start...end] for a fixed score. In each call, it checks all three possible moves. If a move's sum matches the target score, it makes a recursive call for the resulting subproblem and adds 1 (for the current operation). The function returns the maximum value among all valid moves.

class Solution {    public int maxOperations(int[] nums) {        int n = nums.length;        if (n < 2) {            return 0;        }                int maxOps = 0;                // Case 1: Remove first two elements        maxOps = Math.max(maxOps, 1 + solve(nums, 2, n - 1, nums[0] + nums[1]));                // Case 2: Remove last two elements        maxOps = Math.max(maxOps, 1 + solve(nums, 0, n - 3, nums[n - 1] + nums[n - 2]));                // Case 3: Remove first and last elements        maxOps = Math.max(maxOps, 1 + solve(nums, 1, n - 2, nums[0] + nums[n - 1]));                return maxOps;    }     private int solve(int[] nums, int start, int end, int score) {        if (start >= end) {            return 0;        }                int res = 0;                // Option 1: remove from front        if (nums[start] + nums[start + 1] == score) {            res = Math.max(res, 1 + solve(nums, start + 2, end, score));        }                // Option 2: remove from back        if (nums[end] + nums[end - 1] == score) {            res = Math.max(res, 1 + solve(nums, start, end - 2, score));        }                // Option 3: remove from both ends        if (nums[start] + nums[end] == score) {            res = Math.max(res, 1 + solve(nums, start + 1, end - 1, score));        }                return res;    }}

Complexity

Time

O(3^(n/2)) - In the worst-case scenario, each recursive call can branch into three further calls. The depth of the recursion is roughly `n/2`. This leads to an exponential number of function calls, making it too slow for the given constraints.

Space

O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be up to `n/2` in the worst case.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Directly models the decision-making process described in the problem.

Cons

  • Highly inefficient due to the re-computation of the same subproblems.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {private  Integer[][] f;private  int[] nums;private  int s;private  int n;public  int maxOperations(int[] nums) {    this.nums = nums;    n = nums.length;    int a = g(2, n - 1, nums[0] + nums[1]);    int b = g(0, n - 3, nums[n - 2] + nums[n - 1]);    int c = g(1, n - 2, nums[0] + nums[n - 1]);    return 1 + Math.max(a, Math.max(b, c));  }private  int g(int i, int j, int s) {    f = new Integer[n][n];    this.s = s;    return dfs(i, j);  }private  int dfs(int i, int j) {    if (j - i < 1) {      return 0;    }    if (f[i][j] != null) {      return f[i][j];    }    int 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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem