Maximum Sum of Distinct Subarrays With Length K

medium sliding window hash set

Problem

You are given an array of positive integers nums and an integer k. Among all subarrays of nums whose length is exactly k and whose elements are pairwise distinct, find the largest possible sum. If no length-k subarray has all distinct values, return 0.

Inputnums = [1,5,4,2,9,9,9], k = 3

Output15

[4,2,9] sums to 15 with all values distinct; every later window repeats 9, so it cannot count.

nums (comma-separated positive integers)

k (window length)

def maximum_subarray_sum(nums, k):
    freq = {}
    win_sum = 0
    best = 0
    for r, x in enumerate(nums):
        freq[x] = freq.get(x, 0) + 1
        win_sum += x
        if r >= k:
            old = nums[r - k]
            freq[old] -= 1
            if freq[old] == 0:
                del freq[old]
            win_sum -= old
        if r >= k - 1 and len(freq) == k:
            best = max(best, win_sum)
    return best

function maximumSubarraySum(nums, k) {
  const freq = new Map();
  let winSum = 0, best = 0;
  for (let r = 0; r < nums.length; r++) {
    const x = nums[r];
    freq.set(x, (freq.get(x) || 0) + 1);
    winSum += x;
    if (r >= k) {
      const old = nums[r - k];
      if (freq.get(old) === 1) freq.delete(old);
      else freq.set(old, freq.get(old) - 1);
      winSum -= old;
    }
    if (r >= k - 1 && freq.size === k) {
      best = Math.max(best, winSum);
    }
  }
  return best;
}

long maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    long winSum = 0, best = 0;
    for (int r = 0; r < nums.length; r++) {
        int x = nums[r];
        freq.merge(x, 1, Integer::sum);
        winSum += x;
        if (r >= k) {
            int old = nums[r - k];
            if (freq.merge(old, -1, Integer::sum) == 0) freq.remove(old);
            winSum -= old;
        }
        if (r >= k - 1 && freq.size() == k) {
            best = Math.max(best, winSum);
        }
    }
    return best;
}

long long maximumSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    long long winSum = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        int x = nums[r];
        freq[x]++;
        winSum += x;
        if (r >= k) {
            int old = nums[r - k];
            if (--freq[old] == 0) freq.erase(old);
            winSum -= old;
        }
        if (r >= k - 1 && (int)freq.size() == k) {
            best = max(best, winSum);
        }
    }
    return best;
}

Explanation

Because every candidate subarray has the same fixed length k, we never need to grow or shrink a window by varying amounts: we slide a window of exactly k elements one step at a time. The only twist over a plain fixed-window maximum sum is the distinctness rule, and a frequency map handles that.

We keep three things: the running window sum win_sum, a map freq from value to how many times it appears in the window, and the best answer so far. When the right edge reaches index r, we add nums[r] to both the sum and the map; once r >= k, the element nums[r-k] has fallen out of the window, so we subtract it and decrement its count, deleting the key entirely when its count hits zero.

Deleting zero-count keys is the key trick: it means the number of keys in the map equals the number of distinct values in the window. So a window is valid exactly when len(freq) == k — k slots all holding different values. Only then do we let win_sum compete for the answer.

Walking the default example nums = [1,5,4,2,9,9,9], k = 3: window [1,5,4] is distinct with sum 10, [5,4,2] improves to 11, and [4,2,9] improves to 15. After that, [2,9,9] and [9,9,9] both contain 9 more than once, so the map has fewer than 3 keys and they are skipped. The answer stays 15.

Every element is added to the window exactly once and removed at most once, and each add or remove is an O(1) hash-map update, so the whole scan is O(n) time. The map never holds more than k + 1 entries, giving O(k) extra space.

Time: O(n) Space: O(k)