2461 - Maximum Sum of Distinct Subarrays With Length K

Problem

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

• the length of the subarray is k, and
• all the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: [1,5,4] = 10, [5,4,2] = 11, [4,2,9] = 15, [2,9,9] and [9,9,9] have repeats

Input: nums = [4,4,4], k = 3
Output: 0

Constraints:

• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Approach

Move a window of size k across the array, like in 1456. Each step, subtract the number that leaves and add the one that enters, so sum always holds the current window’s total. To know whether all numbers in the window are different, keep a map from each number to how many times it shows up in the window. When a number’s count drops to 0, remove it from the map. Then the map has exactly k keys only when no number repeats, and that’s the only time we compare sum with the best answer.

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        const int n = nums.size();
        long long sum = 0;
        for (int i = 0; i < k; i++) {
            mp[nums[i]]++;
            sum += nums[i];
        }

        long long maxi = (mp.size() == k) ? sum : 0;
        for (int i = 1; i <= n - k; i++) {
            int out = nums[i - 1], in = nums[i + k - 1];

            if (--mp[out] == 0) mp.erase(out);
            mp[in]++;
            sum += in - out;

            if (mp.size() == k) maxi = max(maxi, sum);
        }
        return maxi;
    }
};

• time: O(n)
• space: O(k)