Scale Engineer

Maximize Subarray Sum After Removing All Occurrences of One Element

Hard
#3030Time: O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst case, U can be equal to N, leading to an O(N^2) complexity. Finding unique elements takes O(N). The main loop runs U times. Inside the loop, creating a new array takes O(N) and Kadane's algorithm takes O(N).Space: O(N) to store the unique elements and the temporary array for each unique element.1 company
Patterns
Dynamic Programming
Data structures
ArraySegment Tree
Companies
Rubrik

Prompt

You are given an integer array nums.

You can do the following operation on the array at most once:

  • Choose any integer x such that nums remains non-empty on removing all occurrences of x.
  • Remove all occurrences of x from the array.

Return the maximum subarray sum across all possible resulting arrays.

 

Example 1:

Input: nums = [-3,2,-2,-1,3,-2,3]

Output: 7

Explanation:

We can have the following arrays after at most one operation:

  • The original array is nums = [-3, 2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -3 results in nums = [2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -2 results in nums = [-3, 2, -1, 3, 3]. The maximum subarray sum is 2 + (-1) + 3 + 3 = 7.
  • Deleting all occurences of x = -1 results in nums = [-3, 2, -2, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = 3 results in nums = [-3, 2, -2, -1, -2]. The maximum subarray sum is 2.

The output is max(4, 4, 7, 4, 2) = 7.

Example 2:

Input: nums = [1,2,3,4]

Output: 10

Explanation:

It is optimal to not perform any operations.

 

Constraints:

  • 1 <= nums.length <= 105
  • -106 <= nums[i] <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We first identify all unique numbers in the input array. Then, for each unique number x, we create a new temporary array by removing all occurrences of x. On this new array, we calculate the maximum subarray sum using Kadane's algorithm. We keep track of the overall maximum sum found across all generated arrays, including the original array (which corresponds to not performing any operation).

Algorithm

  • Calculate the maximum subarray sum for the original nums array using Kadane's algorithm and store it as the initial global_max_sum.
  • Find all unique elements in nums and store them in a set.
  • For each unique element x:
    • Check if removing all occurrences of x would make the array empty. If so, continue to the next unique element.
    • Create a new temporary array by filtering out all occurrences of x from nums.
    • Calculate the maximum subarray sum of the temporary array using Kadane's algorithm.
    • Update global_max_sum = max(global_max_sum, new_max_sum).
  • Return global_max_sum.

Walkthrough

The algorithm proceeds as follows:

  1. First, handle the base case of not performing any operation. Calculate the maximum subarray sum of the original nums array using Kadane's algorithm. This value serves as our initial answer.
  2. Find all unique elements in nums. A HashSet is suitable for this, allowing O(n) discovery.
  3. Iterate through each unique element x found in the previous step.
  4. For each x, check if removing it would result in an empty array. If count(x) == nums.length, we cannot remove x, so we skip it.
  5. If removing x is a valid operation, create a new list or array that contains all elements from nums except for x. This takes O(n) time.
  6. Run Kadane's algorithm on this new array to find its maximum subarray sum. Kadane's algorithm finds the maximum sum of a contiguous subarray in O(n) time.
  7. Compare this sum with the overall maximum sum found so far and update it if the new sum is greater.
  8. After checking all unique elements, the value stored as the overall maximum is the answer.

Here is a code snippet for this approach:

import java.util.*; class Solution {    public long maxSubarraySum(int[] nums) {        // Calculate max subarray sum for the original array        long maxSoFar = kadane(nums);         Set<Integer> uniqueNums = new HashSet<>();        Map<Integer, Integer> counts = new HashMap<>();        for (int num : nums) {            uniqueNums.add(num);            counts.put(num, counts.getOrDefault(num, 0) + 1);        }         for (int x : uniqueNums) {            // Check if removing x makes the array empty            if (counts.get(x) == nums.length) {                continue;            }             List<Integer> tempList = new ArrayList<>();            for (int num : nums) {                if (num != x) {                    tempList.add(num);                }            }                        int[] tempArray = tempList.stream().mapToInt(i -> i).toArray();            maxSoFar = Math.max(maxSoFar, kadane(tempArray));        }         return maxSoFar;    }     private long kadane(int[] arr) {        if (arr.length == 0) {            return Long.MIN_VALUE; // Or some other indicator for empty array        }        long maxCurrent = arr[0];        long maxGlobal = arr[0];        for (int i = 1; i < arr.length; i++) {            maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);            if (maxCurrent > maxGlobal) {                maxGlobal = maxCurrent;            }        }        return maxGlobal;    }}

Complexity

Time

O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst case, U can be equal to N, leading to an O(N^2) complexity. Finding unique elements takes O(N). The main loop runs U times. Inside the loop, creating a new array takes O(N) and Kadane's algorithm takes O(N).

Space

O(N) to store the unique elements and the temporary array for each unique element.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem statement.

  • Correct for all cases.

Cons

  • Inefficient for large inputs. An O(N^2) complexity will likely time out given N can be up to 10^5.

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