Problem Statement in English

You’re given an array of integers nums and you need to find the maximum sum of a subarray with all unique elements. The subarray can be of any length, but it must contain only unique elements.

Approach

This is a sliding window problem where we maintain a window of unique elements. We use a set to track the elements in the current window and two pointers to manage the start and end of the window.

Solution in Python


class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()

        l = res = s = 0

        for r, v in enumerate(nums):
            while v in seen:
                s -= nums[l]
                seen.remove(nums[l])
                l += 1

            seen.add(v)
            s += v
            res = max(res, s)

        return res

Complexity

  • Time: $O(n)$
    Since we traverse the array once with two pointers, the time complexity is linear.

  • Space: $O(n)$
    The space complexity is also linear because we use a set to store the elements in the current window.

And we are done.