Maximum Sum of Distinct Subarrays With Length K
Find the maximum sum of a fixed-size subarray where all elements are distinct.
Problem Understanding
Look at every contiguous window of exactly k elements in the integer array nums. Among the windows whose values are all distinct, with no value repeated, return the largest sum.
If every window of length k contains a duplicate, the answer is 0.
Algorithm Strategy
A brute force check for distinctness takes O(k). Doing this for every window results in O(Nk) or O(Nk^2). We need O(N).
Strategy: Fixed Sliding Window + Frequency Map
- Window: Maintain a window of size
k. - Tracking: Use a Hash Map (or frequency array) to count occurrences of each number in the current window.
- Validity: A full window is distinct exactly when the map holds
kdifferent keys (len(counts) == k).- If
count[num] > 1, we have a duplicate.
- If
- Updates:
- Add incoming element: Add it to the sum and increment its count.
- Remove outgoing element: Subtract it from the sum, decrement its count, and delete the key when the count reaches 0.
- If the window holds
kelements and the map holdskkeys, updatemax_sum.
Visual Walkthrough
Watch the window slide: a solid frame marks a full window of different values, and a dashed frame marks one that repeats a value. The counts beside the figure show which value repeats.
Dry Run: [1, 5, 4, 2, 9, 9, 9], k=3
| Window (Indices) | Elements | Map State | Distinct? | Sum | Max |
|---|---|---|---|---|---|
[0, 2] |
[1, 5, 4] |
{1:1, 5:1, 4:1} |
✅ Yes | 10 | 10 |
[1, 3] |
[5, 4, 2] |
{5:1, 4:1, 2:1} |
✅ Yes | 11 | 11 |
[2, 4] |
[4, 2, 9] |
{4:1, 2:1, 9:1} |
✅ Yes | 15 | 15 |
[3, 5] |
[2, 9, 9] |
{2:1, 9:2} |
❌ No (9 is dup) | - | 15 |
[4, 6] |
[9, 9, 9] |
{9:3} |
❌ No | - | 15 |
| Result | 15 |
Edge Cases & Common Mistakes
Edge Cases:
- No distinct window: Return 0, e.g.
nums = [4, 4, 4],k = 3. - k = 1: Every single element is distinct, so the answer is the largest element.
- k = n: There is one window; it counts only if all
nvalues differ.
Common Mistakes:
- Forgetting to delete zero counts: A key left at count 0 keeps the map size too large, so a distinct window is never recognised.
- Comparing before the window is full: Only windows of exactly
kelements count. - Integer overflow: Sums reach
10^5 × 10^5; use a 64-bit type.
Code Solution
Efficient implementation using a Frequency Map.
Maximum Sum of Distinct Subarrays With Length K Code
1var maximumSubarraySum = function(nums, k) {2 let maxSum = 0;3 let currentSum = 0;4 let counts = new Map();56 for (let i = 0; i < nums.length; i++) {7 currentSum += nums[i];8 counts.set(nums[i], (counts.get(nums[i]) || 0) + 1);910 if (i >= k) {11 let out = nums[i - k];12 currentSum -= out;13 counts.set(out, counts.get(out) - 1);14 if (counts.get(out) === 0) counts.delete(out);15 }1617 if (i >= k - 1) {18 if (counts.size === k) {19 maxSum = Math.max(maxSum, currentSum);20 }21 }22 }23 return maxSum;24};