Maximum Erasure Value
Problem
Given an integer array nums, return the maximum possible sum of a subarray with unique elements.
- 1 ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁴
Example
nums = [4,2,4,5,6]17The subarray [2,4,5,6] contains unique elements and has the maximum sum 2 + 4 + 5 + 6 = 17. A brute-force approach would check all subarrays and verify uniqueness, which is inefficient. The optimal solution uses a sliding window to maintain a unique subarray and dynamically adjust its boundaries to maximize the sum.
Approach
Straightforward Solution
A brute-force approach would enumerate all subarrays, check if elements are unique, and compute sums. This leads to O(n^2) or worse time complexity, which is not feasible for large inputs.
Core Observation
The problem requires finding a contiguous subarray with all unique elements and maximum sum. The key is that uniqueness is a constraint on the window, and the sum is the optimization metric.
Path to Optimal
PreviewRecognizing the problem as a sliding window scenario is crucial. The window expands by moving the right pointer forward, adding new elements…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse two pointers to represent the sliding window boundaries. Maintain a set to track elements currently in the window and a running sum of the window's elements…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each element is visited at most twice: once when the right pointer adds it to the window and once when the left pointer removes it. The set operations are O(1) on average, resulting in linear time.
Space
O(n)
The set stores unique elements currently in the window. In the worst case, all elements are unique, so the set size grows to O(n). This auxiliary space is necessary to enforce uniqueness.
Pattern Spotlight
Sliding Window (Dynamic Window with Set for Uniqueness)
When a problem asks for the longest or maximum sum subarray with a uniqueness constraint, use a sliding window that expands until a duplicate is found, then contracts from the left to restore uniqueness, maintaining state incrementally for efficiency.
Solution
| 1 | class Solution: |
| 2 | def maximumUniqueSubarray(self, nums: list[int]) -> int: |
| 3 | seen = set() |
| 4 | left = 0 |
| 5 | curr_sum = 0 |
| 6 | best = 0 |
| 7 | |
| 8 | for right in range(len(nums)): |
| 9 | while nums[right] in seen: |
| 10 | seen.remove(nums[left]) |
| 11 | curr_sum -= nums[left] |
| 12 | left += 1 |
| 13 | |
| 14 | seen.add(nums[right]) |
| 15 | curr_sum += nums[right] |
| 16 | best = max(best, curr_sum) |
| 17 | |
| 18 | return best |
Step-by-Step Solution
Initialize Sliding Window State and Tracking Variables
| 3 | seen = set() |
| 4 | left = 0 |
| 5 | curr_sum = 0 |
| 6 | best = 0 |
Objective
To set up the data structures and variables needed to track the current window's elements, sum, and the best sum found so far.
Key Insight
A set efficiently tracks which elements are currently in the window, enabling O(1) average-time membership checks to detect duplicates. The running sum allows quick updates when the window changes without recomputing sums from scratch. Initializing pointers and accumulators prepares the algorithm for the dynamic window expansion and contraction.
Interview Quick-Check
Core Logic
Using a set to track unique elements enables constant-time detection of duplicates, which is essential for maintaining the sliding window's uniqueness constraint.
State & Boundaries
Initialize left pointer at 0 and accumulators (curr_sum, best) at 0 to represent an empty window and no best sum found yet.
Common Pitfalls & Bugs
Forgetting to initialize the running sum or best sum variables can lead to incorrect results or runtime errors.
Expand Window and Adjust Left Pointer to Maintain Uniqueness
To iterate through the array with the right pointer, expanding the window, and shrink from the left when duplicates are detected to maintain unique elements.
Return the Maximum Sum of a Unique-Element Subarray
To output the maximum sum found after processing all possible unique subarrays.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while nums[right] in seen:While the current element at right pointer is already in the set, shrink the window from the left.
This loop removes elements from the left until the duplicate element at the right pointer is removed, restoring the uniqueness of the window. This dynamic adjustment is the core mechanism that maintains the sliding window's invariant.
best = max(best, curr_sum)Update the best sum if the current window's sum is greater.
Tracking the maximum sum encountered ensures the algorithm returns the correct optimal solution after processing all windows.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does moving the left pointer forward upon encountering a duplicate guarantee that the window will eventually contain unique elements again?
See the answer with Pro.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Maximum Erasure Value from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Erasure Value drill