1695. Maximum Erasure Value

Problem Description

Given an array of positive integers nums, find the maximum sum of a subarray containing only unique elements. The subarray must be contiguous.

Approach 1: Sliding Window with Hash Table

This approach uses a sliding window and a hash table to efficiently track unique elements within the window.

1. Initialization:

   • left: Pointer indicating the start of the sliding window (initially 0).
   • right: Pointer indicating the end of the sliding window (initially 0).
   • sum: Current sum of elements within the window (initially 0).
   • maxSum: Maximum sum encountered so far (initially 0).
   • window: A hash table (dictionary in Python) to store elements within the window and their indices.

2. Sliding Window:

   • Expand the window by moving right to the right.
   • If nums[right] is not in window, add it to window, update sum, and update maxSum.
   • If nums[right] is already in window, it means we have a duplicate. We need to shrink the window from the left until the duplicate is removed.
     • While nums[right] is in window, remove nums[left] from window, update sum, and increment left.

3. Return: maxSum

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the length of nums. Each element is added and removed from the window at most once.
• Space Complexity: O(N) in the worst case, to store the window hash table.

Code Implementation (Python)

def maximumUniqueSubarray(nums):
    left = 0
    right = 0
    sum = 0
    maxSum = 0
    window = {}  # Hash table to store elements and their indices
 
    while right < len(nums):
        if nums[right] not in window:
            window[nums[right]] = right
            sum += nums[right]
            maxSum = max(maxSum, sum)
            right += 1
        else:
            left_index = window[nums[right]]
            while left <= left_index:
                del window[nums[left]]
                sum -= nums[left]
                left += 1
    return maxSum

Approach 2: Prefix Sum and Hash Table

This approach uses a prefix sum array and a hash table to efficiently calculate subarray sums. It's functionally equivalent to Approach 1 but might be slightly less intuitive.

1. Prefix Sum: Calculate the prefix sum array prefixSum, where prefixSum[i] is the sum of nums[0] to nums[i-1].

2. Sliding Window (Implicit): Iterate through nums. For each element nums[i], check its last occurrence using a hash table. If a duplicate is found within the current window (defined by the last occurrence index), adjust the window accordingly.

3. Return: The maximum sum found.

Code Implementation (Python)

from itertools import accumulate
 
def maximumUniqueSubarray(nums):
    prefixSum = list(accumulate(nums, initial=0)) #efficient way to calculate prefix sum using itertools
    d = {} #Hash table to store last occurence
    j = 0
    ans = 0
    for i, v in enumerate(nums):
        if v in d:
            j = max(j, d[v] + 1) #if there is a duplicate, then update the starting point of subarray
        ans = max(ans, prefixSum[i+1] - prefixSum[j]) #find the sum of current subarray
        d[v] = i # update last occurence of current element
    return ans
 
 

Both approaches have the same time and space complexity. Choose the one you find more readable and easier to understand. The sliding window approach (Approach 1) is often considered more intuitive for this type of problem.