Maximum Erasure Value — Solution in Python, Java & C++
Maximum Erasure Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Erasure Value is a medium coding problem on arrays, hash table and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of positive integers nums. Erase one subarray in which all elements are distinct, and score the sum of its elements.
Return the maximum score obtainable.
Example 1
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The best distinct subarray is [4,5,6].
Example 2
Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: Either [5,2,1] or [1,2,5].
Example 3
Input: nums = [7]
Output: 7
Constraints
1 <= nums.length <= 401 <= nums[i] <= 1000
Hints for Maximum Erasure Value
Hint 1
This is the longest-substring-without-repeats window, scored by sum instead of by length.
Hint 2
Keep the window's values in a hash set and its running sum alongside.
Hint 3
When the entering value is already inside, shrink from the left until the duplicate is gone.
How to solve Maximum Erasure Value
It is the longest-substring-without-repeats window, scored by sum: keep a set of the window's values and a running sum, and evict from the left whenever the entering value is already present.
Approach
- For each
right, whilenums[right]is in the set, removenums[left]from the set and the sum, advanceleft. - Add
nums[right]to the set and the sum. - Update the best with the current sum.
Why it works
The window always holds distinct values, and because every value is positive the best distinct window ending at right is the widest one — exactly what the eviction rule maintains.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Evict until the duplicate is gone, not just one element.
Reference solution
Python
def maximumUniqueSubarray(nums) -> int:
seen = set()
left = total = best = 0
for right, x in enumerate(nums):
while x in seen:
seen.discard(nums[left])
total -= nums[left]
left += 1
seen.add(x)
total += x
best = max(best, total)
return bestJava
public static int maximumUniqueSubarray(int[] nums) {
Set<Integer> inWindow = new HashSet<>();
int left = 0, sum = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
while (inWindow.contains(nums[right])) {
inWindow.remove(nums[left]);
sum -= nums[left];
left++;
}
inWindow.add(nums[right]);
sum += nums[right];
if (sum > best) best = sum;
}
return best;
}C++
int maximumUniqueSubarray(vector<int>& nums) {
unordered_set<int> inWindow;
int left = 0, sum = 0, best = 0;
for (int right = 0; right < (int) nums.size(); right++) {
while (inWindow.count(nums[right])) {
inWindow.erase(nums[left]);
sum -= nums[left];
left++;
}
inWindow.insert(nums[right]);
sum += nums[right];
if (sum > best) best = sum;
}
return best;
}JavaScript
var maximumUniqueSubarray = function(nums) {
const inWindow = new Set();
let left = 0, sum = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
while (inWindow.has(nums[right])) {
inWindow.delete(nums[left]);
sum -= nums[left];
left++;
}
inWindow.add(nums[right]);
sum += nums[right];
if (sum > best) best = sum;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets