LeetCode 3487 - Maximum Unique Subarray Sum After Deletion

The problem asks us to find the maximum sum of a subarray from an integer array nums under two key constraints: all elements in the chosen subarray must be unique, and we are allowed to delete any number of elements (except leaving the array empty) before selecting the subarray.

leetcodeeasyarrayhash-tablegreedy

LeetCode Problem 3487

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Greedy

Solution

Problem Understanding

The problem asks us to find the maximum sum of a subarray from an integer array nums under two key constraints: all elements in the chosen subarray must be unique, and we are allowed to delete any number of elements (except leaving the array empty) before selecting the subarray. In other words, we are looking for the largest sum achievable by any subarray that contains no repeated elements.

The input nums is a list of integers ranging from -100 to 100, and its length is up to 100. The output is a single integer representing the maximum sum of a subarray that satisfies the uniqueness constraint. The constraints are small, so even an O(n^2) solution could work, but there is a more elegant O(n) approach using a sliding window.

Important edge cases include arrays with all identical numbers, arrays containing negative numbers, arrays with a mix of positive and negative numbers, and arrays of length 1. The problem guarantees that the array is non-empty, which means we do not have to handle empty inputs.

Approaches

Brute Force

A brute-force approach would involve generating all possible subarrays of nums and checking each subarray for uniqueness. For each unique subarray, we calculate the sum and keep track of the maximum. This approach is correct because it explores all possibilities, but it is inefficient. There are O(n^2) possible subarrays, and checking uniqueness in each subarray can take up to O(n), leading to an O(n^3) time complexity. This is unnecessary for the given constraints and can be optimized.

Optimal Approach

The key observation is that we need a contiguous subarray with unique elements, which naturally lends itself to a sliding window approach. We can maintain a window of unique elements using a hash set. As we iterate through the array, we expand the window by including new elements. If we encounter a duplicate, we shrink the window from the left until the duplicate is removed. During this process, we maintain the sum of the current window and update the maximum sum encountered. This approach works in linear time O(n) because each element is added and removed at most once from the window.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Generate all subarrays and check uniqueness
Optimal O(n) O(n) Sliding window with hash set to maintain uniqueness

Algorithm Walkthrough

  1. Initialize a hash set seen to store the unique elements in the current window.

  2. Initialize two pointers left and right at the start of the array. These will define the current window.

  3. Initialize current_sum to 0 and max_sum to negative infinity (or 0 if we know sums are non-negative).

  4. Iterate through nums with right pointer. For each nums[right]:

  5. While nums[right] is already in seen, remove nums[left] from seen and subtract nums[left] from current_sum. Increment left to shrink the window.

  6. Add nums[right] to seen and add nums[right] to current_sum.

  7. Update max_sum as the maximum of max_sum and current_sum.

  8. After the iteration completes, return max_sum.

Why it works: The sliding window maintains the invariant that all elements between left and right are unique. By expanding the window whenever possible and shrinking it when duplicates are found, we consider all valid subarrays without redundant checks. Maintaining a running sum ensures we can calculate the sum in O(1) for each step.

Python Solution

from typing import List

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        seen = set()
        left = 0
        current_sum = 0
        max_sum = float('-inf')
        
        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 Python solution initializes a hash set seen to track unique elements in the current window. The left pointer marks the start of the window, and current_sum tracks the sum of elements in the window. As we iterate with right, we remove elements from the left until the current element can be added uniquely. We then update the maximum sum. This closely follows the algorithm steps described above.

Go Solution

func maxSum(nums []int) int {
    seen := make(map[int]bool)
    left := 0
    currentSum := 0
    maxSum := -1 << 31
    
    for right := 0; right < len(nums); right++ {
        for seen[nums[right]] {
            delete(seen, nums[left])
            currentSum -= nums[left]
            left++
        }
        seen[nums[right]] = true
        currentSum += nums[right]
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    
    return maxSum
}

In Go, we use a map to track elements in the window because Go does not have a built-in set type. The logic mirrors the Python version. The initial maxSum is set to the minimum integer to handle arrays with all negative numbers. Deletion from the map and updating currentSum maintain the sliding window invariant.

Worked Examples

Example 1: nums = [1,2,3,4,5]

right nums[right] seen current_sum max_sum
0 1 {1} 1 1
1 2 {1,2} 3 3
2 3 {1,2,3} 6 6
3 4 {1,2,3,4} 10 10
4 5 {1,2,3,4,5} 15 15

Return 15.

Example 2: nums = [1,1,0,1,1]

right nums[right] seen current_sum max_sum
0 1 {1} 1 1
1 1 {} → {1} 0 → 1 1
2 0 {1,0} 1 1
3 1 {0,1} 1 1
4 1 {1} 1 1

Return 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is added and removed from the window at most once
Space O(n) Hash set or map stores unique elements in the current window

Because the algorithm iterates through nums once, and every element is processed at most twice, the solution is linear. The hash set or map requires additional space proportional to the number of unique elements in the array.

Test Cases

# Provided examples
assert Solution().maxSum([1,2,3,4,5]) == 15  # all unique, sum entire array
assert Solution().maxSum([1,1,0,1,1]) == 1   # duplicates, only single unique elements can be used
assert Solution().maxSum([1,2,-1,-2,1,0,-1]) == 3  # mix of positive and negative

# Boundary tests
assert Solution().maxSum([100]) == 100  # single element
assert Solution().maxSum([-100]) == -100  # single negative element
assert Solution().maxSum([1]*100) == 1  # all elements identical
assert Solution().maxSum(list(range(1,101))) == 5050  # increasing sequence 1..100

# Stress tests
assert Solution().maxSum([0]*50 + list(range(1,51))) == sum(range(1,51))  # zeros and unique positives
assert Solution().maxSum([-1,-2,-3,-4,-5]) == -1  # all negative elements
Test Why
[1,2,3,4,5] Array entirely unique
[1,1,0,1,1] Array with repeated duplicates
[1,2,-1,-2,1,0,-1] Array with mix of positive and negative numbers
[100] Single element array
[-100] Single negative element
[1]*100 All elements identical
list(range(1,101)) Maximum length with all unique elements
[0]*50 + list(range(1,51)) Zeros and positives combined
`[-1