Max Sum of Distinct Subarrays, Size K
MediumFixed window plus a frequency map
Problem
Return the maximum sum of a size-k subarray whose elements are all distinct (0 if none).
Slide a size-k window, shrinking when a duplicate appears; take the best sum among all-distinct windows.
The idea
Slide a window of size k while maintaining counts of the values inside it. The window is a valid answer only when the map holds exactly k distinct keys, which is the cheap way to say 'no duplicates' without rescanning.
The trick
- Distinct means map size equals the window size.
- Remove the outgoing element's count and delete the key when it reaches zero, or the size is wrong.
- Answer 0 if no window ever qualifies.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — nums=[1,5,4,2,9,9,9], k=3 Values: 1, 5, 4, 2, 9, 9, 9.
1window of size k with a count map and running sum2if map has k distinct: best=max(best,sum)Input
- array
- [1, 5, 4, 2, 9, 9, 9]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 5, 4, 2, 9, 9, 9], k = 3
- Output:
- 15
- Explanation:
- [5,4,2]? best all-distinct window of size 3 sums to 15.
Example 2
- Input:
- nums = [4, 4, 4], k = 3
- Output:
- 0
- Explanation:
- No window of 3 distinct → 0.
Example 3
- Input:
- nums = [9, 9, 9, 1, 2, 3], k = 3
- Output:
- 12
- Explanation:
- [1,2,3] is the only distinct window → 6.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.