Maximum Sum of Almost Unique Subarray — LeetCode 2841 Python Solution

The problem

You are given an integer array nums and two positive integers m and k. Return the maximum sum out of all almost unique subarrays of length k of nums.

Example

Input

nums = [2,6,7,3,1,7], m = 3, k = 4

Output

18

Explanation

There are 3 almost unique subarrays of size k = 4. These subarrays are [2, 6, 7, 3], [6, 7, 3, 1], and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3] which has a sum of 18.

Python solution

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        cnt = Counter(nums[:k])
        s = sum(nums[:k])
        ans = s if len(cnt) >= m else 0
        for i in range(k, len(nums)):
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            s += nums[i] - nums[i - k]
            if cnt[nums[i - k]] == 0:
                cnt.pop(nums[i - k])
            if len(cnt) >= m:
                ans = max(ans, s)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2841. Maximum Sum of Almost Unique Subarray is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems