Leetcode: 2461. Maximum Sum of Distinct Subarrays With Length K

Understand the problem

Given an integer array \(a\) and an integer \(k\). Find the maximum subarray sum of all subarrays of length \(k\) with \(k\) distinct values.

Useful prompts

Can we formulate the problem as sliding window? Since \(n \leq 10^5\), we have to solve the problem in linear time. So, a Sliding Window of size \(k\) can help with that.

Devise a plan

Create a window of length \(k\) and slide it from left to right. For every new valid window (ones that contains \(k\) distinct elements), pick it sum if it greater to the best result so far. Time complexity is \(O(n)\) and space is \(O(1)\).

Carry out the plan

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        N = len(nums)
        freq = Counter(nums[:k])
        cur = sum(nums[:k])
        ans = cur if len(freq) == k else 0
        for i in range(k, N):
            x, y = nums[i - k], nums[i]
            cur += y - x
            freq[x] -= 1
            freq[y] += 1
            if freq[x] == 0:
                freq.pop(x)
            if len(freq) == k and ans < cur:
                ans = cur
        return ans