Maximum Erasure Value asks you to find the maximum sum of a subarray that contains only unique elements. You are given an array of positive integers and you want to 'erase' a contiguous sequence of unique numbers to get the highest score.
This is a quintessential Sliding Window interview question asked by Microsoft, Meta, and Google. It tests whether a candidate can efficiently manage a dynamic range of elements. It also evaluates knowledge of Hash Sets for uniqueness checks and the ability to maintain a running sum, which is more efficient than re-calculating the sum for every window.
The problem is solved using the Sliding Window pattern with a Hash Set. You maintain two pointers, left and right. You expand the window by moving right and adding the element to the sum and the set. If you encounter a duplicate, you shrink the window from the left (subtracting from sum and removing from set) until the duplicate is gone. Throughout the process, you keep track of the maximum sum observed.
Array: [4, 2, 4, 5, 6]
A common error is not using a Hash Set to track uniqueness, which can lead to O(n²) if you search the window manually. Another mistake is forgetting to subtract the removed element from the running sum when shrinking the window. Some also struggle with the boundary conditions of the while loop used for shrinking the window.
Sliding Window is one of the most common patterns for array/string problems. Whenever you hear 'contiguous subarray' and a 'uniqueness' or 'constraint' condition, your mind should immediately go to the two-pointer sliding window technique.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Minimum Consecutive Cards to Pick Up | Medium | Solve | |
| Maximum Sum of Distinct Subarrays With Length K | Medium | Solve | |
| Fruit Into Baskets | Medium | Solve | |
| Count the Number of Good Subarrays | Medium | Solve | |
| Count Complete Subarrays in an Array | Medium | Solve |
