Maximum Erasure Value - Solution & Explanation
Problem Statement
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] <= 104
Approach Overview
Problem 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 1: Sliding Window with HashSet
The sliding window technique can be used here to find the maximum sum of a subarray with unique elements. The idea is to maintain a window with unique elements using a HashSet. Start with two pointers, both at the beginning of the array. As you extend the window by moving the right pointer, check if the current element is already in the HashSet:
- If not, add it to the set and update the maximum sum if needed.
- If it is, move the left pointer until the duplicate element is removed from the set.
This Python function uses a sliding window approach with a HashSet to track the current subarray of unique elements. Two pointers are maintained: left and right. The right pointer expands the window, and whenever a duplicate is found, the left pointer moves forward to remove duplicates. This ensures the subarray between left and right remains unique, while continually updating the maximum score.
Complexity
Time Complexity: O(n), where n is the size of the input array, because each element will be visited at most twice.
Space Complexity: O(min(n, m)), where m is the maximum possible number of unique elements (10,000 in this case).
Approach 2: Optimized Sliding Window using HashMap
By using a HashMap, it can be optimized to store the last occurrence index of each element. While iterating, if a duplicate is found, directly jump the left pointer to the element's next position after its last occurrence:
- Maintain a current sum of the window using two pointers.
- Update the maximum score whenever a valid unique subarray is identified.
This JavaScript solution uses a HashMap (lastOccurrence) to keep track of the indices at which elements last appeared. As the right pointer moves, if a duplicate is encountered, the left pointer quickly jumps to one position after the last occurrence of the duplicate, maintaining an efficient window of unique elements.
Code
JavaScript
C#
Complexity
Time Complexity: O(n), each element is processed once and the sum of subarrays is managed efficiently.
Space Complexity: O(n) due to the use of a HashMap for last occurrences.
Approach 3: Array or Hash Table + Prefix Sum
We use an array or hash table d to record the last occurrence position of each number, and use a prefix sum array s to record the sum from the starting point to the current position. We use a variable j to record the left endpoint of the current non-repeating subarray.
We iterate through the array. For each number v, if d[v] exists, we update j to max(j, d[v]), which ensures that the current non-repeating subarray does not contain v. Then we update the answer to max(ans, s[i] - s[j]), and finally update d[v] to i.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Approach 4: Two Pointers (Sliding Window)
The problem is essentially asking us to find the longest subarray where all elements are distinct. We can use two pointers i and j to point to the left and right boundaries of the subarray, initially i = 0 and j = 0. Additionally, we use a hash table vis to record the elements in the subarray.
We iterate through the array. For each number x, if x is in vis, we continuously remove nums[i] from vis until x is no longer in vis. This way, we find a subarray that contains no duplicate elements. We add x to vis, update the subarray sum s, and then update the answer ans = max(ans, s).
After the iteration, we can get the maximum subarray sum.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with HashSet | Time Complexity: O(n), where n is the size of the input array, because each element will be visited at most twice. |
| Optimized Sliding Window using HashMap | Time Complexity: O(n), each element is processed once and the sum of subarrays is managed efficiently. |
| Array or Hash Table + Prefix Sum | — |
| Two Pointers (Sliding Window) | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Erasure Value | 2 Approaches | Leetcode 1695 | codestorywithMIK • codestorywithMIK • 7,036 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Erasure Value easy or hard?
How to solve Maximum Erasure Value in O(n)?
What is the best approach for Maximum Erasure Value?
What data structure is used in Maximum Erasure Value?
What is the time complexity of Maximum Erasure Value?
Maximum Erasure Value Python or Java solution approach?
Is Maximum Erasure Value asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Erasure Value with our built-in code editor and test cases.
Practice on FleetCode