Maximum Erasure Value: Sliding Window with Unique Elements

LeetCode's Maximum Erasure Value (problem 1695) asks you to find the maximum sum of a contiguous subarray where every element is unique. You are given an array of positive integers nums, and you need to erase (select) a subarray with all distinct values that maximizes the total sum.

For example, given nums = [4, 2, 4, 5, 6], the answer is 17, from the subarray [2, 4, 5, 6].

Why this problem matters

This is a classic "variable-size sliding window" problem that combines two fundamental ideas: maintaining a window of unique elements and tracking a running sum. It shows up frequently in interviews because it tests whether you can handle window state management beyond just counting characters. Here, you need to keep both a set (for uniqueness) and a running sum (for the score) in sync as the window grows and shrinks.

The key insight

You want the longest subarray with all unique elements, but not just the longest. You want the one with the highest sum. The trick is that you can use the same sliding window technique from "Longest Substring Without Repeating Characters," but instead of tracking window length, you track the window's running sum.

Keep a set of values currently in the window. Expand the right pointer one element at a time. When you encounter a value already in the set, shrink from the left, removing values from the set and subtracting them from the running sum, until the duplicate is gone. After each expansion, compare the current sum to the best so far.

Because every element enters and leaves the window at most once, the total work is O(n).

The solution

def maximumUniqueSubarray(nums):
    seen = set()
    left = 0
    window_sum = 0
    max_score = 0

    for right in range(len(nums)):
        while nums[right] in seen:
            seen.remove(nums[left])
            window_sum -= nums[left]
            left += 1

        seen.add(nums[right])
        window_sum += nums[right]
        max_score = max(max_score, window_sum)

    return max_score

The structure follows the standard sliding window template. The for loop advances right one position per iteration, growing the window. The while loop shrinks from the left whenever the new element is a duplicate. After resolving any duplicate, you add the new element to the set, update the running sum, and check if you have a new best.

The key difference from the "longest substring" variant is the window_sum variable. Every time you add an element on the right, you add its value to window_sum. Every time you remove an element on the left, you subtract its value. This keeps the sum perfectly synchronized with what is actually in the window, without ever recalculating it from scratch.

Visual walkthrough

Let's trace through nums = [4, 2, 4, 5, 6] step by step. The left pointer is in orange, the right pointer is in green.

The answer is 17. The subarray [2, 4, 5, 6] has all unique elements and the highest possible sum. Notice how when we hit the second 4 at index 2, we only needed to remove one element (the first 4 at index 0) before the duplicate was cleared. Then the window kept growing through the rest of the array.

Complexity analysis

Time: O(n). Each element is added to the set exactly once and removed at most once. The right pointer visits every index once. The left pointer also visits each index at most once. Total operations: at most 2n.

Space: O(n). The set stores at most n unique values (when all elements are distinct). The running sum and pointers use O(1) extra space. In the worst case, the set holds every element in the array.

The building blocks

1. Sliding window with variable size

The core mechanic: right always moves forward, left moves forward only when the window becomes invalid. Both pointers are monotonically increasing, which guarantees linear time.

left = 0
for right in range(len(nums)):
    while window_is_invalid():
        left += 1
    update_best()

This template is the skeleton of every variable-size sliding window problem. What changes between problems is the validity condition and what state you track. The expand-and-shrink loop structure stays identical.

2. Set for uniqueness tracking

A set gives you O(1) lookups to check if a value is already in the window. Every time the window grows, add the new element. Every time it shrinks, remove the departing element. The set always reflects exactly what is inside the current window.

while nums[right] in seen:
    seen.remove(nums[left])
    left += 1
seen.add(nums[right])

This same pattern appears in "Longest Substring Without Repeating Characters" and many other sliding window problems that require uniqueness. The only addition here is the running sum, which follows the same add/remove rhythm as the set.

Edge cases

Before submitting, verify your solution handles:

• Single element [5]: return 5. The window is just that one element.
• All identical [3, 3, 3, 3]: return 3. The window never grows past length 1.
• All unique [1, 2, 3, 4, 5]: return 15. The window grows to the full length without ever shrinking.
• Duplicate at the end [1, 2, 3, 1]: return 6, from the subarray [1, 2, 3] or [2, 3, 1], both summing to 6.
• Large values: elements can be up to 10,000, so sums can be large. Python handles big integers natively, but in other languages, make sure your sum variable is wide enough.

The sliding window solution handles all of these without special cases.

From understanding to recall

Reading this walkthrough takes a few minutes. Reproducing the solution from scratch next week is a different challenge. The pattern here, maintaining a set and a running sum inside a variable-size sliding window, is a building block that appears in dozens of problems. Spaced repetition helps you internalize it: you revisit the set-tracking and sum-tracking mechanics at increasing intervals, writing the code each time, until the pattern is automatic.

Related posts

• Longest Substring Without Repeating Characters - The classic uniqueness-in-a-window problem, using a set without the sum tracking
• Find All Anagrams in a String - Fixed-size sliding window with frequency counting instead of a set
• Minimum Window Substring - The "shrinking window" variant where you minimize instead of maximize

If you want to make this pattern stick, practice it at spaced intervals. Each repetition strengthens the connection between "unique elements in a subarray" and the set-plus-sliding-window approach.