What pattern does Maximum Erasure Value use?

The Pattern: Sliding Window (Dynamic Window with Set for Uniqueness) The Heuristic: When a problem asks for the longest or maximum sum subarray with a uniqueness constraint, use a sliding window that expands until a duplicate is found, then contracts from the left to restore uniqueness, maintaining state incrementally for efficiency.

Maximum Erasure Value - LeetCode Solution

Q: What is the time complexity of Maximum Erasure Value?

O(n). Each element is visited at most twice: once when the right pointer adds it to the window and once when the left pointer removes it. The set operations are O(1) on average, resulting in linear time.

Problem

Given an integer array nums, return the maximum possible sum of a subarray with unique elements.

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁴

Example

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

Output: 17

The subarray [2,4,5,6] contains unique elements and has the maximum sum 2 + 4 + 5 + 6 = 17. A brute-force approach would check all subarrays and verify uniqueness, which is inefficient. The optimal solution uses a sliding window to maintain a unique subarray and dynamically adjust its boundaries to maximize the sum.

Approach

Straightforward Solution

A brute-force approach would enumerate all subarrays, check if elements are unique, and compute sums. This leads to O(n^2) or worse time complexity, which is not feasible for large inputs.

Core Observation

The problem requires finding a contiguous subarray with all unique elements and maximum sum. The key is that uniqueness is a constraint on the window, and the sum is the optimization metric.

Path to Optimal

Recognizing the problem as a sliding window scenario is crucial. The window expands by moving the right pointer forward, adding new elements. When a duplicate is detected, the left pointer moves forward, removing elements until uniqueness is restored. This dynamic adjustment maintains a unique window and allows tracking the sum efficiently.

Optimal Approach

Use two pointers to represent the sliding window boundaries. Maintain a set to track elements currently in the window and a running sum of the window's elements. Expand the right pointer, adding elements and updating the sum and set. When a duplicate is encountered, shrink the window from the left, removing elements and updating the sum and set until the duplicate is removed. Track the maximum sum encountered during this process.

Time

O(n)

Each element is visited at most twice: once when the right pointer adds it to the window and once when the left pointer removes it. The set operations are O(1) on average, resulting in linear time.

Space

O(n)

The set stores unique elements currently in the window. In the worst case, all elements are unique, so the set size grows to O(n). This auxiliary space is necessary to enforce uniqueness.

Solution

1class Solution:
  def maximumUniqueSubarray(self, nums: list[int]) -> int:
      seen = set()
      left = 0
      curr_sum = 0
      best = 0
7
      for right in range(len(nums)):
          while nums[right] in seen:
              seen.remove(nums[left])
              curr_sum -= nums[left]
              left += 1
13
          seen.add(nums[right])
          curr_sum += nums[right]
          best = max(best, curr_sum)
17
      return best

Step-by-Step Solution

1

Initialize Sliding Window State and Tracking Variables

3seen = set()
4left = 0
5curr_sum = 0
6best = 0

Objective

To set up the data structures and variables needed to track the current window's elements, sum, and the best sum found so far.

Key Insight

A set efficiently tracks which elements are currently in the window, enabling O(1) average-time membership checks to detect duplicates. The running sum allows quick updates when the window changes without recomputing sums from scratch. Initializing pointers and accumulators prepares the algorithm for the dynamic window expansion and contraction.

Interview Quick-Check

Core Logic

Using a set to track unique elements enables constant-time detection of duplicates, which is essential for maintaining the sliding window's uniqueness constraint.

State & Boundaries

Initialize left pointer at 0 and accumulators (curr_sum, best) at 0 to represent an empty window and no best sum found yet.

Common Pitfalls & Bugs

Forgetting to initialize the running sum or best sum variables can lead to incorrect results or runtime errors.

2

Expand Window and Adjust Left Pointer to Maintain Uniqueness

8for right in range(len(nums)):
  while nums[right] in seen:
      seen.remove(nums[left])
      curr_sum -= nums[left]
      left += 1
  seen.add(nums[right])
  curr_sum += nums[right]
  best = max(best, curr_sum)

Objective

To iterate through the array with the right pointer, expanding the window, and shrink from the left when duplicates are detected to maintain unique elements.

Key Insight

The while loop inside the for loop ensures that whenever a duplicate element is encountered at the right pointer, the window shrinks from the left until the duplicate is removed. This dynamic adjustment maintains the invariant that the window contains only unique elements. Updating the set and running sum incrementally during expansion and contraction avoids recomputing sums and membership from scratch, enabling efficient O(n) time complexity.

Interview Quick-Check

Core Logic

The nested while loop removes elements from the left until the duplicate at the right pointer is eliminated, preserving the uniqueness constraint of the sliding window.

State & Boundaries

The for loop moves the right pointer forward through the array, while the inner while loop moves the left pointer forward as needed to restore uniqueness.

Common Pitfalls & Bugs

Failing to update the running sum and set correctly when moving the left pointer leads to incorrect window sums and duplicate detection.

Complexity

Each element is added and removed from the set at most once, ensuring O(n) time complexity.

3

Return the Maximum Sum of a Unique-Element Subarray

18	`return best`

Objective

To output the maximum sum found after processing all possible unique subarrays.

Key Insight

After the sliding window has traversed the entire array, the variable tracking the best sum holds the maximum sum of any subarray with unique elements. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Returning the best sum variable provides the final answer, which was updated whenever a larger unique subarray sum was found.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

while nums[right] in seen:

While the current element at right pointer is already in the set, shrink the window from the left.

This loop removes elements from the left until the duplicate element at the right pointer is removed, restoring the uniqueness of the window. This dynamic adjustment is the core mechanism that maintains the sliding window's invariant.

Line 16 Critical

best = max(best, curr_sum)

Update the best sum if the current window's sum is greater.

Tracking the maximum sum encountered ensures the algorithm returns the correct optimal solution after processing all windows.

Line 3 Core

seen = set()

Initialize a set to track unique elements in the current window.

The set enables O(1) average-time membership checks, which is essential for efficiently detecting duplicates and maintaining the uniqueness constraint of the sliding window.

Line 10 Core

seen.remove(nums[left])

Remove the element at the left pointer from the set.

Removing this element updates the set to reflect the current window contents and is necessary to eliminate duplicates and maintain correctness.

Line 11 Core

curr_sum -= nums[left]

Subtract the element at the left pointer from the running sum.

Updating the running sum when shrinking the window ensures the sum accurately reflects the current window's elements without recomputing from scratch.

Line 14 Core

seen.add(nums[right])

Add the current element at the right pointer to the set.

Including the new element in the set updates the window's unique elements and prepares for sum calculation.

Line 15 Core

curr_sum += nums[right]

Add the current element at the right pointer to the running sum.

Updating the running sum incrementally allows efficient tracking of the window's total without recomputing sums.

Line 4 Core

left = 0

Initialize the left pointer of the sliding window at the start of the array.

The left pointer marks the start of the current window and moves forward to shrink the window when duplicates are found, maintaining the window's uniqueness.

Line 5 Core

curr_sum = 0

Initialize the running sum of the current window to zero.

Maintaining a running sum allows efficient updates when the window expands or contracts without recomputing sums from scratch.

Line 6 Core

best = 0

Initialize the variable to track the best (maximum) sum found so far.

This variable stores the maximum sum of any unique-element subarray encountered during the traversal, enabling the algorithm to return the correct final result.

Line 12 Core

left += 1

Move the left pointer forward to shrink the window.

Advancing the left pointer reduces the window size and helps remove duplicates, maintaining the uniqueness constraint.

Line 18 Core

return best

Return the maximum sum of a unique-element subarray found.

This final return statement outputs the solution computed by the sliding window traversal, completing the algorithm.

Line 8 Standard

for right in range(len(nums)):

Iterate through the array with the right pointer to expand the sliding window.

The right pointer moves forward to include new elements in the window, exploring all possible subarrays starting from the left pointer.

Test Your Understanding

Why does moving the left pointer forward upon encountering a duplicate guarantee that the window will eventually contain unique elements again?

Because removing elements from the left shrinks the window and eliminates the earlier occurrence(s) of the duplicate, restoring the uniqueness property. Since the window only moves forward, this process ensures no duplicates remain.

Don't just read it. Drill it.

Reconstruct Maximum Erasure Value from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Erasure Value drill

or drill a free problem

1	`class Solution:`
2	`def maximumUniqueSubarray(self, nums: list[int]) -> int:`
3	`seen = set()`
4	`left = 0`
5	`curr_sum = 0`
6	`best = 0`
7
8	`for right in range(len(nums)):`
9	`while nums[right] in seen:`
10	`seen.remove(nums[left])`
11	`curr_sum -= nums[left]`
12	`left += 1`
13
14	`seen.add(nums[right])`
15	`curr_sum += nums[right]`
16	`best = max(best, curr_sum)`
17
18	`return best`

3	`seen = set()`
4	`left = 0`
5	`curr_sum = 0`
6	`best = 0`

8	`for right in range(len(nums)):`
9	`while nums[right] in seen:`
10	`seen.remove(nums[left])`
11	`curr_sum -= nums[left]`
12	`left += 1`
14	`seen.add(nums[right])`
15	`curr_sum += nums[right]`
16	`best = max(best, curr_sum)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Sliding Window State and Tracking Variables

Expand Window and Adjust Left Pointer to Maintain Uniqueness

Return the Maximum Sum of a Unique-Element Subarray

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.