#1695

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Erasure Value

Maximize the score by erasing a subarray with unique elements in an array of integers.

Problem Statement

You are given an array of positive integers, nums. Your task is to erase exactly one subarray from nums such that the subarray contains only unique elements. The score you get from this operation is the sum of all the elements in the subarray.

Return the maximum possible score you can achieve by erasing such a subarray. A subarray is defined as a contiguous subsequence, meaning the elements of the subarray are consecutive in the original array.

Examples

Example 1

Input: nums = [4,2,4,5,6]

Output: 17

The optimal subarray here is [2,4,5,6].

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]

Output: 8

The optimal subarray here is [5,2,1] or [1,2,5].

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 104

Solution Approach

Sliding Window with Hash Map

Iterate through the array with two pointers and use a hash map to track the last seen position of each element. When encountering a duplicate, move the left pointer to maintain uniqueness of the subarray. This ensures an optimal solution with O(n) time complexity.

Maximizing the Sum of Subarray

As you slide through the array, compute the sum of the elements within the current subarray. If a duplicate is found, adjust the window and calculate the new sum. Keep track of the maximum sum found during the process.

Space Complexity Considerations

The space complexity is O(n) due to the storage required for the hash map. However, this is necessary to maintain quick lookups for the uniqueness of elements in the current subarray.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since we process each element once and use a hash map for constant-time lookups and updates. The space complexity is O(n) due to the hash map storing the last seen indices of elements in the array.

What Interviewers Usually Probe

Can the candidate implement a sliding window efficiently with hash lookups?
Does the candidate demonstrate the ability to optimize space and time complexity using hash maps?
How well does the candidate handle edge cases like arrays with minimal or repetitive values?

Common Pitfalls or Variants

Common pitfalls

Failing to handle duplicate values correctly when adjusting the window.
Not updating the sum efficiently after modifying the sliding window.
Overcomplicating the solution with unnecessary nested loops or extra space.

Follow-up variants

What if the array contains only one element?
How would the solution change if the elements in the array were sorted?
What if the problem required finding the maximum product instead of the sum?

FAQ

What is the main strategy for solving Maximum Erasure Value?

The primary strategy is using a sliding window and a hash map to ensure the subarray contains unique elements while maximizing the sum.

How do I handle duplicates in the array for this problem?

Duplicates can be handled by adjusting the left pointer of the sliding window whenever a duplicate is encountered, ensuring uniqueness of the subarray.

Can this problem be solved with a brute force approach?

While a brute force approach is possible, it would be inefficient with a time complexity of O(n^2). A sliding window approach with a hash map is much more optimal.

What is the time complexity of the optimal solution for this problem?

The optimal solution has a time complexity of O(n) because each element is processed once, and hash lookups take constant time.

What would be the space complexity for this problem?

The space complexity is O(n) due to the hash map used to store the last seen positions of elements in the array.

terminal

Solution

Solution 1: Array or Hash Table + Prefix Sum

We use an array or hash table $\text{d}$ to record the last occurrence position of each number, and use a prefix sum array $\text{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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        d = [0] * (max(nums) + 1)
        s = list(accumulate(nums, initial=0))
        ans = j = 0
        for i, v in enumerate(nums, 1):
            j = max(j, d[v])
            ans = max(ans, s[i] - s[j])
            d[v] = i
        return ans

Solution 2: 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 $\text{vis}$ to record the elements in the subarray.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        d = [0] * (max(nums) + 1)
        s = list(accumulate(nums, initial=0))
        ans = j = 0
        for i, v in enumerate(nums, 1):
            j = max(j, d[v])
            ans = max(ans, s[i] - s[j])
            d[v] = i
        return ans

Continue Practicing

#1658 minimum operations to reduce x to zero #1477 find two non overlapping sub arrays each with target sum #2009 minimum number of operations to make array continuous