Best Distinct Window Sum
MediumSliding Window
Problem
A playlist assigns a popularity score to each track in nums (tracks with equal scores are considered duplicates). A radio block plays exactly k consecutive tracks, and no two tracks in a block may be duplicates.
Return the largest total score of any valid block of k consecutive tracks, or 0 if no block is valid.
Example 1
- Input:
- nums = [3, 8, 3, 1, 6, 6, 2], k = 3
- Output:
- 12
Valid blocks: [8, 3, 1] = 12 and [3, 1, 6] = 10. The others repeat a 3 or a 6.
Example 2
- Input:
- nums = [7, 7, 7], k = 2
- Output:
- 0
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^5
Hint
Show the first hint
Two things change as a window of size k slides: its sum and its multiset of values.
Walkthrough
How to approach it
01Clarify before coding
- What if no window is valid? Return 0 (scores are positive, so any valid answer is > 0).
- Is the window length exactly k? Yes.
- Can the sum overflow 32 bits? Up to 10^5 · 10^5 = 10^10: use 64-bit in typed languages.
02Brute force
For each window, build a set and a sum from scratch.
Cost: O(n·k) time, too slow when k is large.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.