1695: Maximum Erasure Value

Difficulty: Medium

Topics: Arrays, Sliding Window, Hash Table

Companies: Google, Amazon, Microsoft

Pro Tip: For subarray problems with unique elements, the sliding window technique is often the most efficient solution. Maintain a window with unique elements and adjust it dynamically when duplicates appear.

Problem Statement

You are given an array of positive integers nums. You need to find the maximum sum of any contiguous subarray containing only unique elements. Return the maximum score achievable by erasing exactly one such subarray.

Example 1

Input: nums = [4,2,4,5,6]

Output: 17

Explanation: The optimal subarray is [2,4,5,6] with sum 2+4+5+6=17

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]

Output: 8

Explanation: The optimal subarrays are [5,2,1] or [1,2,5] with sum 8

Problem Link: View on LeetCode ↗

Key Insight

The problem requires finding a contiguous subarray with all unique elements that has the maximum possible sum. The optimal solutions leverage:

Sliding Window Technique: Maintain a window of unique elements by expanding with new elements and contracting when duplicates appear
Efficient Tracking: Use a set or map to track elements in the current window
Sum Optimization: Maintain a running sum that adjusts dynamically as the window changes

Important: The solution must efficiently handle arrays up to 10⁵ elements, requiring O(n) time complexity.

Approach 1: Sliding Window with Set

Maintain a window [i, j) of unique elements using two pointers and a hash set.

Algorithm Steps

Initialize two pointers i=0, j=0 and maxSum = 0
Initialize a set to track elements in current window
Initialize currentSum = 0
While j < length:
- If nums[j] not in set:
  - Add nums[j] to set
  - Add nums[j] to currentSum
  - Update maxSum = max(maxSum, currentSum)
  - j++
- Else:
  - Remove nums[i] from set
  - Subtract nums[i] from currentSum
  - i++
Return maxSum

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(n)

Each element is processed at most twice (once by each pointer). The set uses O(n) space.

Sliding Window with Set

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> unique;
        int maxSum = 0, currentSum = 0;
        int i = 0, j = 0;
        int n = nums.size();
        
        while (j < n) {
            if (unique.find(nums[j]) == unique.end()) {
                unique.insert(nums[j]);
                currentSum += nums[j];
                maxSum = max(maxSum, currentSum);
                j++;
            } else {
                unique.erase(nums[i]);
                currentSum -= nums[i];
                i++;
            }
        }
        return maxSum;
    }
};

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> unique = new HashSet<>();
        int maxSum = 0, currentSum = 0;
        int i = 0, j = 0;
        int n = nums.length;
        
        while (j < n) {
            if (!unique.contains(nums[j])) {
                unique.add(nums[j]);
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
                j++;
            } else {
                unique.remove(nums[i]);
                currentSum -= nums[i];
                i++;
            }
        }
        return maxSum;
    }
}

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        unique = set()
        max_sum = current_sum = i = 0
        n = len(nums)
        
        for j in range(n):
            while nums[j] in unique:
                unique.remove(nums[i])
                current_sum -= nums[i]
                i += 1
            unique.add(nums[j])
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
            
        return max_sum

Implementation Note: This approach efficiently maintains a window of unique elements. The Python version uses a different loop structure to avoid redundant checks.

Approach 2: Prefix Sum with HashMap

Use prefix sums for efficient range sum calculation and a hashmap to track last seen indices.

Algorithm Steps

Compute prefix sum array where prefix[i] = sum of nums[0..i-1]
Initialize maxSum = 0 and start = 0
Use a map to store last occurrence index of each value
For each index i:
- If nums[i] exists in map and last index ≥ start: update start to last_index + 1
- Update current sum = prefix[i+1] - prefix[start]
- Update maxSum = max(maxSum, current sum)
- Update map with current index
Return maxSum

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(n)

Requires one pass through the array and O(n) space for prefix sums and map.

Prefix Sum with HashMap

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n+1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i+1] = prefix[i] + nums[i];
        }
        
        unordered_map<int, int> last_seen;
        int maxSum = 0;
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            if (last_seen.count(nums[i]) && last_seen[nums[i]] >= start) {
                start = last_seen[nums[i]] + 1;
            }
            last_seen[nums[i]] = i;
            int currentSum = prefix[i+1] - prefix[start];
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }
};

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; i++) {
            prefix[i+1] = prefix[i] + nums[i];
        }
        
        Map<Integer, Integer> lastSeen = new HashMap<>();
        int maxSum = 0;
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            if (lastSeen.containsKey(nums[i]) && lastSeen.get(nums[i]) >= start) {
                start = lastSeen.get(nums[i]) + 1;
            }
            lastSeen.put(nums[i], i);
            int currentSum = prefix[i+1] - prefix[start];
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n+1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
            
        last_seen = {}
        max_sum = start = 0
        
        for i, num in enumerate(nums):
            if num in last_seen and last_seen[num] >= start:
                start = last_seen[num] + 1
            last_seen[num] = i
            current_sum = prefix[i+1] - prefix[start]
            max_sum = max(max_sum, current_sum)
            
        return max_sum

Implementation Note: This approach efficiently calculates subarray sums using prefix sums and handles duplicates by updating the start index based on last seen positions.

Approach 3: Optimized Sliding Window with Frequency Array

Use an array to track character frequency for O(1) lookups, optimized for given constraints.

Algorithm Steps

Initialize frequency array of size max_value+1 (max_value=10⁴ per constraints)
Initialize left=0, currentSum=0, maxSum=0
For right in [0, n):
- Increment frequency of nums[right]
- Add nums[right] to currentSum
- While frequency[nums[right]] > 1:
  - Decrement frequency of nums[left]
  - Subtract nums[left] from currentSum
  - left++
- Update maxSum = max(maxSum, currentSum)
Return maxSum

Complexity Analysis

Time Complexity	Space Complexity
O(n)	O(max_value)

More efficient than set-based approach for constrained value ranges.

Frequency Array Solution

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        vector<bool> freq(10001, false);
        int maxSum = 0, currentSum = 0;
        int left = 0, n = nums.size();
        
        for (int right = 0; right < n; right++) {
            while (freq[nums[right]]) {
                freq[nums[left]] = false;
                currentSum -= nums[left];
                left++;
            }
            freq[nums[right]] = true;
            currentSum += nums[right];
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }
};

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        boolean[] freq = new boolean[10001];
        int maxSum = 0, currentSum = 0;
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            while (freq[nums[right]]) {
                freq[nums[left]] = false;
                currentSum -= nums[left];
                left++;
            }
            freq[nums[right]] = true;
            currentSum += nums[right];
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        freq = [False] * 10001
        max_sum = current_sum = left = 0
        
        for right in range(len(nums)):
            while freq[nums[right]]:
                freq[nums[left]] = False
                current_sum -= nums[left]
                left += 1
            freq[nums[right]] = True
            current_sum += nums[right]
            max_sum = max(max_sum, current_sum)
            
        return max_sum

Implementation Note: This approach is optimized for the problem constraints where nums[i] ≤ 10,000. It uses a boolean array for O(1) lookups.

Approach Comparison

Approach	Best For	Time	Space
Sliding Window with Set	General case with no value constraints	O(n)	O(n)
Prefix Sum with HashMap	When range sums are needed frequently	O(n)	O(n)
Frequency Array	Constrained value ranges (nums[i] ≤ 10⁴)	O(n)	O(max_value)

Important: For the given constraints (n ≤ 10⁵, nums[i] ≤ 10⁴), the frequency array approach is most efficient.

Edge Cases and Testing

1. All Unique Elements

Input: [1,2,3,4,5] → Output: 15 (sum of entire array)

2. All Elements Identical

Input: [3,3,3,3] → Output: 3 (single element)

3. Alternating Duplicates

Input: [1,2,1,2,1,2] → Output: 3 (subarray [1,2] or [2,1])

4. Large Input Size

Input: Array of 10⁵ distinct elements → Output: sum of entire array

5. Single Element

Input: [5] → Output: 5

Warning: Always test with maximum size input to ensure O(n) performance and avoid timeouts.

Frequently Asked Questions

1. Why is the sliding window approach efficient?

The sliding window approach processes each element at most twice (once by each pointer), resulting in O(n) time complexity - optimal for large inputs.

2. How does the frequency array improve performance?

By using direct array indexing instead of hash operations, it reduces constant factors in time complexity, especially beneficial for constrained value ranges.

3. Can we use a bitset instead of boolean array?

Yes, but boolean arrays are more space-efficient in most languages. A bitset would save space but add minor access overhead.

4. Why use prefix sums in Approach 2?

Prefix sums allow O(1) range sum queries, making it efficient to calculate subarray sums when we know the start and end indices.

5. How to handle negative numbers?

The problem specifies positive integers only, so negative cases don't need handling. For general integers, we'd need different approaches.

6. Is the subarray contiguous?

Yes, the problem requires a contiguous subarray with unique elements that has the maximum sum.

7. Why is the answer unique?

While there might be multiple subarrays with the same maximum sum, the problem guarantees the maximum sum is unique.

8. Can we solve this with dynamic programming?

Possible but less efficient. DP would typically require O(n²) time, which is infeasible for n=10⁵.

9. What if there are multiple duplicates?

The algorithms naturally handle multiple duplicates by adjusting the window start to the last occurrence index + 1.

10. How to modify for longest unique subarray?

Instead of tracking sum, track window length: maxLen = max(maxLen, right-left+1). The core sliding window logic remains similar.

Final Insight: This problem demonstrates how different implementations of the sliding window technique can optimize for various constraints. The frequency array approach is particularly efficient for bounded value ranges common in programming problems.