Is Maximum Erasure Value easy or hard?

Maximum Erasure Value is considered a medium difficulty problem. The challenge comes from combining two techniques: sliding window pointer movement and hash-based duplicate detection while maintaining a running subarray sum.

How to solve Maximum Erasure Value in O(n)?

Maintain two pointers representing a sliding window and a hash structure to track elements inside the window. Expand the right pointer while values remain unique and accumulate the sum. If a duplicate appears, move the left pointer forward and remove elements until the window becomes unique again.

What is the best approach for Maximum Erasure Value?

The best approach uses a sliding window with a hash set or hash map. Two pointers maintain a window of unique elements while a running sum tracks the subarray value. Each element is processed at most twice, giving O(n) time complexity and O(n) extra space.

What data structure is used in Maximum Erasure Value?

The solution relies on a hash-based structure such as a HashSet or HashMap to detect duplicates in constant time. Combined with the sliding window technique, this allows efficient maintenance of a subarray containing only unique elements.

What is the time complexity of Maximum Erasure Value?

The optimal sliding window solution runs in O(n) time because each element is added to and removed from the window at most once. Hash lookups for duplicates take O(1) average time. Space complexity is O(n) for the set or map storing elements currently in the window.

Maximum Erasure Value Python or Java solution approach?

Both Python and Java implementations follow the same logic: maintain a sliding window with two pointers and track elements using a set or map. Update a running sum when expanding or shrinking the window. This produces an O(n) time solution with O(n) additional space.

Is Maximum Erasure Value asked at Google, Amazon, or Meta?

Maximum Erasure Value reflects a common interview pattern involving sliding windows and hash tables. Variations of the problem appear in interviews at companies like Amazon, Google, and Meta when evaluating a candidate's ability to manage dynamic subarrays with uniqueness constraints.

Description Hints 2 Solution Video 32:19

1695. Maximum Erasure Value

Medium64.2% acceptance7 companies

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 <= 10⁵
1 <= nums[i] <= 10⁴

Asked at 7 companies

AT&T Cashfree

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

The main point here is for the subarray to contain unique elements for each index. Only the first subarrays starting from that index have unique elements.

Hint 2

This can be solved using the two pointers technique

32:19

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution