We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Erasure Value

Number: 1813

Difficulty: Medium

Paid? No

Companies: Amazon, Cashfree

Problem Description

Given an array of positive integers nums, find exactly one contiguous subarray that contains only unique elements such that the sum of this subarray is maximized. The answer is the maximum sum obtainable from any such unique-element subarray.

Key Insights

  • Use a sliding window to maintain a subarray with unique elements.
  • A set or hash map is used to efficiently track and check for duplicates.
  • Expand the window while elements are unique, and contract it when a duplicate is encountered.
  • Maintain a running sum for the current window and update the maximum sum when applicable.

Space and Time Complexity

Time Complexity: O(n) – each element is processed once. Space Complexity: O(n) – additional space is used for the set/hash map in the worst case.

Solution

We solve the problem using the sliding window technique. Two pointers (left and right) define the current window of unique elements. As we iterate over the array with the right pointer, we add the current element to the running sum and the set. If a duplicate is encountered, we move the left pointer forward until the duplicate is removed from the set, deducting the removed elements from the running sum. At each step, we update the maximum sum if the current sum is higher than the previously computed maximum. This approach efficiently finds the maximum sum of a contiguous subarray with unique elements.

Code Solutions

# Python solution using sliding window
def maximumUniqueSubarray(nums):
    # Set to store unique elements in the current window
    unique_numbers = set()
    left = 0  # left pointer for the sliding window
    current_sum = 0  # current sum of the sliding window
    max_sum = 0  # maximum sum found

    # Iterate with right pointer over the array
    for right in range(len(nums)):
        # If duplicate is found, shrink window from the left until duplicate is removed
        while nums[right] in unique_numbers:
            unique_numbers.remove(nums[left])
            current_sum -= nums[left]
            left += 1
        # Add the new unique element to the set and current sum
        unique_numbers.add(nums[right])
        current_sum += nums[right]
        # Update maximum sum if current window sum is higher
        max_sum = max(max_sum, current_sum)
    return max_sum

# Example usage:
print(maximumUniqueSubarray([4,2,4,5,6]))  # Expected output: 17
← Back to All Questions