Watch 10 video solutions for Maximum Erasure Value, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by codestorywithMIK has 6,682 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.
Return the maximum score you can get by erasing exactly one subarray.
An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).
Example 1:
Input: nums = [4,2,4,5,6] Output: 17 Explanation: The optimal subarray here is [2,4,5,6].
Example 2:
Input: nums = [5,2,1,2,5,2,1,2,5] Output: 8 Explanation: The optimal subarray here is [5,2,1] or [1,2,5].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 104Problem Overview: You are given an integer array and need the maximum possible sum of a subarray containing only unique elements. If a duplicate appears, the subarray must shrink until all elements are distinct again.
Approach 1: Brute Force Enumeration (O(n²) time, O(n) space)
Start every subarray from index i and extend it forward while tracking seen values in a set. As soon as a duplicate appears, stop expanding that subarray and move to the next starting index. Maintain a running sum for the current subarray and update the maximum sum seen so far. This approach is straightforward but inefficient because each index can start a new scan across the array, leading to quadratic time. It helps build intuition before moving to a sliding window technique commonly used in array problems.
Approach 2: Sliding Window with HashSet (O(n) time, O(n) space)
Use the classic two‑pointer sliding window technique. Maintain a left and right pointer representing the current window and a HashSet storing elements inside the window. Expand the right pointer while elements remain unique, adding each value to the set and updating a running sum. When a duplicate appears, move the left pointer forward, removing elements from the set and subtracting their values from the sum until the duplicate disappears. Each element enters and leaves the window at most once, giving linear time. This approach directly combines sliding window logic with fast membership checks from a hash table.
Approach 3: Optimized Sliding Window with HashMap (O(n) time, O(n) space)
Instead of shrinking the window one element at a time, store the last index of each value in a HashMap. When you encounter a duplicate at index r, jump the left boundary directly to lastIndex[value] + 1. Maintain prefix sums or a running sum to quickly recompute the window total after the jump. This avoids repeated removals and keeps the window adjustments constant time. The technique is especially useful when duplicates appear far apart because the window can skip large sections instantly.
Recommended for interviews: Interviewers typically expect the sliding window solution with a set or map. The brute force approach demonstrates you understand the uniqueness constraint, but the linear-time sliding window shows mastery of pointer movement and hash lookups. Many subarray with unique elements problems reduce to this same pattern, so recognizing it quickly is a strong signal during coding interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set | O(n²) | O(n) | For understanding the problem or when constraints are very small |
| Sliding Window with HashSet | O(n) | O(n) | General optimal solution for arrays with uniqueness constraints |
| Optimized Sliding Window with HashMap | O(n) | O(n) | When you want faster window jumps by tracking last seen indices |