Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

LeetCode 1695, Maximum Erasure Value

Problem Understanding

This problem asks us to find a contiguous subarray that contains only unique elements, meaning no value appears more than once inside that subarray. Among all such valid subarrays, we must return the maximum possible sum of its elements.

The input is an array nums consisting of positive integers. Since all numbers are positive, adding more unique elements always increases the total sum. This observation becomes important when designing the optimal solution.

A subarray must be contiguous. We cannot skip elements or rearrange them. For example, in [4,2,4,5,6], the subarray [2,4,5,6] is valid because it appears consecutively in the original array.

The output is a single integer representing the largest sum obtainable from exactly one subarray whose elements are all distinct.

The constraints are important:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

An array size of 10^5 immediately tells us that quadratic solutions will likely be too slow. We need an algorithm close to linear time.

Because all values are positive integers, several useful properties emerge:

Expanding a valid unique window increases the sum.
Once duplicates appear, we should shrink the window only enough to restore uniqueness.
We never benefit from removing unique positive numbers unnecessarily.

Some important edge cases include:

Arrays with all unique values, where the entire array is the answer.
Arrays where every element is identical, where the best answer is just one element.
Duplicates appearing far apart, which tests whether the sliding window adjusts correctly.
Very small arrays such as length 1.

Approaches

Brute Force Approach

The brute force solution checks every possible subarray.

For each starting index i, we expand the subarray toward the right while tracking whether all elements remain unique. We can use a hash set to detect duplicates. As long as the current subarray contains unique values, we compute its sum and update the answer.

This works because every possible contiguous subarray is examined, so the maximum valid sum will eventually be found.

However, there are O(n^2) possible subarrays. Even if duplicate detection is efficient using a hash set, the total number of examined elements becomes too large for n = 10^5.

Therefore, the brute force solution is too slow.

Optimal Sliding Window Approach

The key observation is that we only care about subarrays with unique elements. This naturally suggests a sliding window.

We maintain a window [left, right] that always contains unique elements.

As we expand the right boundary:

If the new element is not already inside the window, we simply include it.
If the new element creates a duplicate, we repeatedly move the left boundary forward until the duplicate is removed.

Since all values are positive, keeping the window as large as possible is always beneficial. We never need to shrink the window unless uniqueness is violated.

A hash set allows constant time duplicate checks, while a running sum allows constant time window sum updates.

Each element enters and leaves the window at most once, giving linear time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks every possible subarray
Optimal	O(n)	O(n)	Sliding window with hash set and running sum

Algorithm Walkthrough

Initialize two pointers, left and right, representing the current sliding window boundaries.
Create a hash set called seen to store all unique elements currently inside the window. This allows constant time duplicate detection.
Maintain a variable current_sum representing the sum of elements inside the current window.
Maintain another variable max_sum storing the best answer found so far.
Iterate through the array using right.
For each new element nums[right], check whether it already exists in seen.
If it is already present, the window is no longer valid because duplicates are not allowed. Repeatedly:

Remove nums[left] from seen
Subtract it from current_sum
Move left forward

Continue shrinking until the duplicate element is removed and the window becomes unique again.
Add nums[right] to seen.
Add nums[right] to current_sum.
Update max_sum with the larger value between the current answer and current_sum.
Continue until all elements have been processed.

Why it works

The sliding window always maintains the invariant that all elements inside the window are unique. Whenever a duplicate appears, the left pointer advances just enough to restore validity.

Because every number is positive, a larger valid window always produces a greater or equal sum than a smaller version of the same window. Therefore, maintaining the largest possible unique window at every step guarantees that we eventually discover the maximum achievable sum.

Each element is inserted into the window once and removed once, which ensures linear complexity.

Python Solution

from typing import List

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()
        
        left = 0
        current_sum = 0
        max_sum = 0
        
        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                current_sum -= nums[left]
                left += 1
            
            seen.add(nums[right])
            current_sum += nums[right]
            
            max_sum = max(max_sum, current_sum)
        
        return max_sum

The implementation follows the sliding window algorithm directly.

The seen set stores all elements currently inside the window. Before adding a new value, we check whether it already exists in the set. If it does, the window becomes invalid, so we repeatedly remove elements from the left side until the duplicate disappears.

The variable current_sum tracks the sum of the current window incrementally. This avoids recomputing sums repeatedly, which would increase the complexity.

The max_sum variable is updated after every valid expansion of the window.

Because each element is added and removed at most once, the algorithm runs efficiently in linear time.

Go Solution

func maximumUniqueSubarray(nums []int) int {
    seen := make(map[int]bool)

    left := 0
    currentSum := 0
    maxSum := 0

    for right := 0; right < len(nums); right++ {
        for seen[nums[right]] {
            seen[nums[left]] = false
            currentSum -= nums[left]
            left++
        }

        seen[nums[right]] = true
        currentSum += nums[right]

        if currentSum > maxSum {
            maxSum = currentSum
        }
    }

    return maxSum
}

The Go implementation mirrors the Python solution closely.

Instead of a Python set, Go uses a map[int]bool to track which elements currently exist inside the sliding window.

Go does not have a built in max function for integers, so the comparison is written manually.

Integer overflow is not an issue under the given constraints because the maximum possible sum is at most 10^5 * 10^4 = 10^9, which safely fits inside Go's standard integer type on LeetCode environments.

Worked Examples

Example 1

Input:

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

Step	right	nums[right]	Action	Window	current_sum	max_sum
1	0	4	Add 4	[4]	4	4
2	1	2	Add 2	[4,2]	6	6
3	2	4	Duplicate detected	shrink window
4	2	4	Remove left 4	[2]	2	6
5	2	4	Add 4	[2,4]	6	6
6	3	5	Add 5	[2,4,5]	11	11
7	4	6	Add 6	[2,4,5,6]	17	17

Final answer:

Example 2

Input:

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

Step	right	nums[right]	Action	Window	current_sum	max_sum
1	0	5	Add 5	[5]	5	5
2	1	2	Add 2	[5,2]	7	7
3	2	1	Add 1	[5,2,1]	8	8
4	3	2	Duplicate detected	shrink
5	3	2	Remove 5	[2,1]	3	8
6	3	2	Remove 2	[1]	1	8
7	3	2	Add 2	[1,2]	3	8
8	4	5	Add 5	[1,2,5]	8	8
9	5	2	Duplicate detected	shrink
10	5	2	Remove 1	[2,5]	7	8
11	5	2	Remove 2	[5]	5	8
12	5	2	Add 2	[5,2]	7	8

The remaining iterations continue similarly, and the maximum sum remains 8.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the sliding window at most once
Space	O(n)	The hash set may store up to all unique elements

The algorithm is linear because both pointers only move forward. Even though there is a nested while loop, the total number of left pointer movements across the entire algorithm is at most n.

The extra memory comes from the hash set storing elements currently inside the window.

Test Cases

from typing import List

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()
        
        left = 0
        current_sum = 0
        max_sum = 0
        
        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                current_sum -= nums[left]
                left += 1
            
            seen.add(nums[right])
            current_sum += nums[right]
            
            max_sum = max(max_sum, current_sum)
        
        return max_sum

sol = Solution()

assert sol.maximumUniqueSubarray([4,2,4,5,6]) == 17  # provided example 1
assert sol.maximumUniqueSubarray([5,2,1,2,5,2,1,2,5]) == 8  # provided example 2

assert sol.maximumUniqueSubarray([1]) == 1  # single element
assert sol.maximumUniqueSubarray([5,5,5,5]) == 5  # all duplicates
assert sol.maximumUniqueSubarray([1,2,3,4,5]) == 15  # all unique
assert sol.maximumUniqueSubarray([2,1,2,3,4]) == 10  # duplicate near beginning
assert sol.maximumUniqueSubarray([1,2,1,3,4]) == 10  # shrinking window
assert sol.maximumUniqueSubarray([10000]) == 10000  # maximum value
assert sol.maximumUniqueSubarray([1,1,2,2,3,3]) == 5  # repeated pairs
assert sol.maximumUniqueSubarray([9,1,2,3,9]) == 15  # duplicate at ends

Test	Why
`[4,2,4,5,6]`	Validates standard duplicate handling
`[5,2,1,2,5,2,1,2,5]`	Tests repeated shrinking and expansion
`[1]`	Smallest possible input
`[5,5,5,5]`	All elements identical
`[1,2,3,4,5]`	Entire array is valid
`[2,1,2,3,4]`	Duplicate appears after expansion
`[1,2,1,3,4]`	Window must shrink correctly
`[10000]`	Tests upper value range
`[1,1,2,2,3,3]`	Multiple duplicate transitions
`[9,1,2,3,9]`	Duplicate far apart

Edge Cases

One important edge case is when all elements are already unique. For example, [1,2,3,4,5]. A buggy implementation might unnecessarily shrink the window or fail to compute the full sum correctly. In this situation, the sliding window simply expands through the entire array, and the final answer becomes the total sum of all elements.

Another important case occurs when every element is the same, such as [7,7,7,7]. Here, every new element immediately creates a duplicate. The algorithm repeatedly removes the old occurrence before adding the new one. The largest valid subarray therefore contains only one element, and the implementation correctly returns 7.

A more subtle edge case is when duplicates appear far apart, such as [9,1,2,3,9]. A naive implementation might incorrectly reset the entire window upon seeing the second 9. The sliding window solution only removes elements until the duplicate disappears, preserving as much of the valid subarray as possible. This ensures the optimal subarray [1,2,3,9] is discovered.

Another potential source of bugs is handling the running sum while shrinking the window. If values are removed from the set but not subtracted from the sum, the computed answer becomes incorrect. The implementation updates both structures together, guaranteeing consistency between the window contents and its recorded sum.

LeetCode 1695 - Maximum Erasure Value