Problem Description

You have an integer array nums and an integer k. Your task is to find the maximum sum among all subarrays that satisfy two specific conditions:

1. The subarray must have exactly k elements
2. All elements in the subarray must be distinct (no duplicates)

A subarray is a contiguous sequence of elements from the original array. For example, if nums = [1, 2, 3], then [1, 2] and [2, 3] are subarrays, but [1, 3] is not.

You need to examine all possible subarrays of length k and check if they contain only unique elements. Among all valid subarrays (those with distinct elements), return the one with the maximum sum. If no subarray of length k has all distinct elements, return 0.

For example:

• If nums = [1, 5, 4, 2, 9, 9, 9] and k = 3, the subarrays of length 3 are: [1, 5, 4], [5, 4, 2], [4, 2, 9], [2, 9, 9], and [9, 9, 9]. Only [1, 5, 4], [5, 4, 2], and [4, 2, 9] have all distinct elements. Their sums are 10, 11, and 15 respectively, so the answer is 15.

• If nums = [4, 4, 4] and k = 3, the only subarray [4, 4, 4] contains duplicate elements, so the answer is 0.

Intuition

The key insight is that we need to check every possible subarray of length k to find the one with maximum sum that has all distinct elements. Since we're looking at consecutive subarrays of fixed length, this naturally suggests using a sliding window approach.

Think of it like a window of size k that slides over the array from left to right. Initially, the window covers elements from index 0 to k-1. Then we slide it one position to the right, removing the leftmost element and adding a new element from the right.

To efficiently check if all elements in the current window are distinct, we need to track the frequency of each element. A hash table (or Counter in Python) is perfect for this - we can maintain counts of all elements currently in the window. When all elements are distinct, each element appears exactly once, so the size of our hash table equals k.

As we slide the window:

1. Add the new element entering the window (increment its count)
2. Remove the element leaving the window (decrement its count)
3. If an element's count drops to 0, remove it from the hash table entirely
4. Update the window sum by adding the new element and subtracting the removed element

The beauty of this approach is that we don't need to recalculate the sum from scratch for each window - we can update it incrementally by just adjusting for the element that entered and the element that left. Similarly, we don't need to rebuild the frequency map each time; we just update it for the two elements that changed.

Whenever the hash table size equals k (meaning all elements are distinct), we check if the current sum is larger than our maximum found so far.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window technique combined with a hash table to efficiently track distinct elements and their counts.

Initial Setup:

1. Create a Counter cnt to store the frequency of elements in the first window (elements from index 0 to k-1)
2. Calculate the initial sum s of the first k elements
3. Initialize the answer ans - if the first window has all distinct elements (checked by len(cnt) == k), set ans = s, otherwise ans = 0

Sliding the Window: Starting from index k, we iterate through the rest of the array. For each step:

1. Add the new element:

   • cnt[nums[i]] += 1 - increment the count of the element entering the window
   • s += nums[i] - add it to the running sum

2. Remove the old element:

   • cnt[nums[i - k]] -= 1 - decrement the count of the element leaving the window
   • If the count becomes 0, remove it from the hash table: cnt.pop(nums[i - k])
   • s -= nums[i - k] - subtract it from the running sum

3. Check validity and update answer:

   • If len(cnt) == k, all elements in the current window are distinct
   • Update ans = max(ans, s) if the current sum is larger

Why this works:

• The Counter maintains exact frequencies of elements in the current window
• When len(cnt) == k, it means we have exactly k different elements, each appearing once
• The running sum s is maintained incrementally by adding the new element and subtracting the old one, avoiding recalculation
• Time complexity is O(n) where n is the length of the array, as we visit each element once
• Space complexity is O(k) for storing at most k elements in the Counter

The algorithm efficiently finds the maximum sum among all valid subarrays without having to recompute everything for each window position.

Example Walkthrough

Let's walk through the solution with nums = [1, 5, 4, 2, 9, 9, 9] and k = 3.

Initial Setup (First Window: [1, 5, 4])

• Create Counter: cnt = {1: 1, 5: 1, 4: 1}
• Calculate initial sum: s = 1 + 5 + 4 = 10
• Check if valid: len(cnt) = 3 = k ✓ (all elements distinct)
• Initialize answer: ans = 10

Slide 1: Move to [5, 4, 2] (i = 3)

• Add new element nums[3] = 2:
  • cnt[2] += 1 → cnt = {1: 1, 5: 1, 4: 1, 2: 1}
  • s = 10 + 2 = 12
• Remove old element nums[0] = 1:
  • cnt[1] -= 1 → count becomes 0, so remove from cnt
  • cnt = {5: 1, 4: 1, 2: 1}
  • s = 12 - 1 = 11
• Check validity: len(cnt) = 3 = k ✓
• Update answer: ans = max(10, 11) = 11

Slide 2: Move to [4, 2, 9] (i = 4)

• Add new element nums[4] = 9:
  • cnt[9] += 1 → cnt = {5: 1, 4: 1, 2: 1, 9: 1}
  • s = 11 + 9 = 20
• Remove old element nums[1] = 5:
  • cnt[5] -= 1 → count becomes 0, so remove from cnt
  • cnt = {4: 1, 2: 1, 9: 1}
  • s = 20 - 5 = 15
• Check validity: len(cnt) = 3 = k ✓
• Update answer: ans = max(11, 15) = 15

Slide 3: Move to [2, 9, 9] (i = 5)

• Add new element nums[5] = 9:
  • cnt[9] += 1 → cnt = {4: 1, 2: 1, 9: 2}
  • s = 15 + 9 = 24
• Remove old element nums[2] = 4:
  • cnt[4] -= 1 → count becomes 0, so remove from cnt
  • cnt = {2: 1, 9: 2}
  • s = 24 - 4 = 20
• Check validity: len(cnt) = 2 ≠ k ✗ (has duplicates)
• Answer remains: ans = 15

Slide 4: Move to [9, 9, 9] (i = 6)

• Add new element nums[6] = 9:
  • cnt[9] += 1 → cnt = {2: 1, 9: 3}
  • s = 20 + 9 = 29
• Remove old element nums[3] = 2:
  • cnt[2] -= 1 → count becomes 0, so remove from cnt
  • cnt = {9: 3}
  • s = 29 - 2 = 27
• Check validity: len(cnt) = 1 ≠ k ✗ (has duplicates)
• Answer remains: ans = 15

Final Result: 15 (from the subarray [4, 2, 9])

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm uses a sliding window approach with a fixed window size k. Initially, it processes the first k elements to build the counter and calculate the initial sum, which takes O(k) time. Then it iterates through the remaining n - k elements once. In each iteration, it performs constant-time operations:

• Adding and updating a counter entry: O(1) average case for dictionary operations
• Removing a counter entry if needed: O(1) average case
• Updating the running sum: O(1)
• Checking the counter size and updating the maximum: O(1)

Since k ≤ n, the total time complexity is O(k) + O(n - k) = O(n).

Space Complexity: O(k), which can be considered O(n) in the worst case when k = n.

The space is primarily used by the Counter object cnt, which stores at most k distinct elements at any given time (since we're maintaining a sliding window of size k). In the worst case where all elements in the window are distinct, the counter will have exactly k entries. Since k can be at most n, the space complexity is O(min(k, n)), which simplifies to O(n) in the worst case.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Initial Window Properly

A common mistake is not checking if the first window (indices 0 to k-1) contains all distinct elements before starting the sliding process. This can lead to missing a valid maximum sum if it occurs in the first window.

Incorrect approach:

max_sum = 0  # Always starting with 0, ignoring the first window
for i in range(k, len(nums)):
    # sliding window logic...

Correct approach:

# Check the first window explicitly
max_sum = current_sum if len(element_count) == k else 0

2. Incorrectly Managing the Counter When Removing Elements

When an element leaves the window, simply decrementing its count isn't enough. If the count reaches zero, the element must be completely removed from the counter. Otherwise, len(element_count) will give an incorrect count of distinct elements.

Incorrect approach:

element_count[nums[i - k]] -= 1
# Forgetting to remove the key when count becomes 0

Correct approach:

element_count[nums[i - k]] -= 1
if element_count[nums[i - k]] == 0:
    element_count.pop(nums[i - k])

3. Using a Set Instead of a Counter

Some might think to use a set to track distinct elements, but this fails when the same element appears multiple times in the window.

Incorrect approach:

window_set = set(nums[:k])
# This loses frequency information

Why it fails: If nums = [1, 2, 3, 1, 5] and k = 3, the window [3, 1, 5] would appear to have 3 distinct elements in a set, but we wouldn't know that when we slide to include the second 1, we now have a duplicate.

4. Off-by-One Errors in Window Boundaries

Ensuring the window contains exactly k elements and correctly identifying which element to add and remove can be tricky.

Common mistake:

# Wrong indices for removal
element_count[nums[i - k + 1]] -= 1  # Should be nums[i - k]

Correct indexing:

• When at index i, the window spans from i - k + 1 to i
• The element to remove is at index i - k
• The element to add is at index i