Given an integer array nums and an integer k, find the maximum sum among all subarrays of length k that have all distinct elements. Return 0 if no such subarray exists.

Examples

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: Subarrays of length 3 with distinct elements:
  [1,5,4] sum=10, [5,4,2] sum=11, [4,2,9] sum=15
  [2,9,9] has duplicate, [9,9,9] has duplicate
  Maximum = 15

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: [4,4,4] has duplicates, no valid subarray exists.

Constraints

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

Thinking Process

Two Constraints on the Window

The sliding window must satisfy:

  1. Length exactly k – standard fixed-size window
  2. All distinct elements – no duplicates inside

When a duplicate enters, we can’t just shrink by one – we must shrink past the previous occurrence of that duplicate to restore uniqueness.

Algorithm

Use a hash map numToIdx tracking the last seen index of each element. For each new end:

  1. Look up the last occurrence of nums[end]
  2. Shrink begin past that occurrence (to remove the duplicate)
  3. Also shrink if window exceeds size k
  4. If window size equals k, update the answer

The running sum currSum is maintained incrementally as we shrink/expand.

Walk-through

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

end=0: [1]         currSum=1,  size=1
end=1: [1,5]       currSum=6,  size=2
end=2: [1,5,4]     currSum=10, size=3 → rtn=10
end=3: shrink(size>k) → [5,4,2]  currSum=11, size=3 → rtn=11
end=4: shrink(size>k) → [4,2,9]  currSum=15, size=3 → rtn=15
end=5: 9 seen at idx=4, shrink past 4 → [9]  currSum=9, size=1
end=6: 9 seen at idx=5, shrink past 5 → [9]  currSum=9, size=1

Answer: 15 ✓
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
# Distinct windows of size 3: [1,5,4]=10, [5,4,2]=11, [4,2,9]=15

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: ### Two Constraints on the Window

How the code works:

  1. Length exactly k – standard fixed-size window
  2. All distinct elements – no duplicates inside
  3. Look up the last occurrence of nums[end]
  4. Shrink begin past that occurrence (to remove the duplicate)
  5. Also shrink if window exceeds size k
  6. If window size equals k, update the answer

Walkthrough — input nums = [1,5,4,2,9,9,9], k = 3, expected output 15:

Subarrays of length 3 with distinct elements: [1,5,4] sum=10, [5,4,2] sum=11, [4,2,9] sum=15 [2,9,9] has duplicate, [9,9,9] has duplicate Maximum = 15

Key Details

Why begin <= lastOccur (not <)? We need to move begin past the previous occurrence, so we shrink while begin is still at or before lastOccur.

Why combine both conditions in one while? A single shrink loop handles both constraints simultaneously:

  • end - begin + 1 > k enforces the size limit
  • begin <= lastOccur enforces uniqueness

Why long long? With 10^5 elements each up to 10^5, the sum can reach 10^{10}.

Common Mistakes

  • Only checking window size without handling duplicates (misses the distinct constraint)
  • Not updating numToIdx after shrinking (stale indices cause incorrect shrinks)
  • Using a frequency map + separate duplicate counter instead of last-index tracking (works but more complex)

Key Takeaways

  • “Fixed-size window + all distinct” = sliding window with last-occurrence tracking
  • Storing the index of the last occurrence (not just frequency) lets us jump begin directly past the duplicate
  • The combined shrink condition handles both constraints elegantly in one loop

References

Template Reference