Maximum Sum of Distinct Subarrays With Length K
Problem
Given an integer array nums and an integer k, return the maximum sum of a subarray of size k that contains only distinct elements. If no such subarray exists, return 0.
- 1 ≤ k ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁵
Example
nums = [1,2,7,7,4,3,6], k = 313Consider subarrays of size 3: [1,2,7] sums to 10 with distinct elements; [2,7,7] contains duplicates; [7,7,4] contains duplicates; [7,4,3] sums to 14 with distinct elements; [4,3,6] sums to 13 with distinct elements. The maximum sum among these is 14 from [7,4,3]. However, since the problem requires distinct elements, the subarray [7,4,3] is valid and sums to 14, which is the maximum. The algorithm uses a sliding window to track counts and sums, shrinking the window when duplicates or size constraints are violated, and updates the maximum sum when the window size equals k.
Approach
Straightforward Solution
A brute-force approach would check every subarray of size k, verifying distinctness and summing elements, resulting in O(n*k) time complexity, which is too slow for large inputs.
Core Observation
The problem requires finding a fixed-size subarray with all distinct elements and maximum sum. The key is to maintain a sliding window of size at most k, ensuring no duplicates inside it, and efficiently update the sum and maximum.
Path to Optimal
The key recognition signals are 'subarray of size k', 'distinct elements', and 'maximum sum'. These indicate a Sliding Window pattern with a frequency map to track duplicates. The algorithm maintains a window with two pointers, expanding the right pointer and updating counts and sums. When duplicates or size constraints are violated, the left pointer moves forward to restore validity. This approach achieves O(n) time by processing each element at most twice.
Optimal Approach
Use a sliding window with two pointers, a hash map to count element frequencies, and a running sum. Expand the right pointer, add the new element to the count and sum. While the window contains duplicates or exceeds size k, shrink from the left, updating counts and sum accordingly. When the window size equals k and all elements are distinct, update the maximum sum. Return the maximum sum found or 0 if none.
Time
O(n)
Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it. All hash map operations are O(1) on average.
Space
O(k)
The frequency map stores counts of elements currently in the window, which can be at most k distinct elements. This auxiliary space scales linearly with k.
Pattern Spotlight
Sliding Window (Fixed-Size with Distinctness Constraint)
Maintain a window that expands until constraints break, then contract from the left to restore validity, using a frequency map to detect duplicates and a running sum to track the window's total efficiently.
Solution
| 1 | class Solution: |
| 2 | def maximumSubarraySum(self, nums, k): |
| 3 | |
| 4 | count = {} |
| 5 | left = 0 |
| 6 | curr_sum = 0 |
| 7 | best = 0 |
| 8 | |
| 9 | for right in range(len(nums)): |
| 10 | |
| 11 | n = nums[right] |
| 12 | count[n] = count.get(n, 0) + 1 |
| 13 | curr_sum += n |
| 14 | |
| 15 | while count[n] > 1 or right - left + 1 > k: |
| 16 | |
| 17 | left_val = nums[left] |
| 18 | count[left_val] -= 1 |
| 19 | |
| 20 | if count[left_val] == 0: |
| 21 | del count[left_val] |
| 22 | |
| 23 | curr_sum -= left_val |
| 24 | left += 1 |
| 25 | |
| 26 | if right - left + 1 == k: |
| 27 | best = max(best, curr_sum) |
| 28 | |
| 29 | return best |
Step-by-Step Solution
Initialize Sliding Window State and Counters
| 4 | count = {} |
| 5 | left = 0 |
| 6 | curr_sum = 0 |
| 7 | best = 0 |
Objective
To set up the data structures and variables needed to track element counts, window boundaries, current sum, and best sum.
Key Insight
A hash map (dictionary) is essential to track the frequency of each element in the current window, enabling quick detection of duplicates. Two pointers define the window boundaries, and a running sum allows efficient calculation of the window's total without recomputing sums repeatedly. Initializing these variables prepares the algorithm for a linear scan with dynamic window resizing.
Interview Quick-Check
Core Logic
The frequency map tracks counts of elements in the window, enabling O(1) duplicate detection.
State & Boundaries
Left pointer starts at 0, representing the start of the window; right pointer will iterate through the array.
Common Pitfalls & Bugs
Forgetting to initialize the running sum or best sum variables can lead to incorrect or missing results.
Expand Window and Update Counts and Sum
| 9 | for right in range(len(nums)): |
| 11 | n = nums[right] |
| 12 | count[n] = count.get(n, 0) + 1 |
| 13 | curr_sum += n |
Objective
To iterate through the array, expanding the window by moving the right pointer, updating element counts and the current sum accordingly.
Key Insight
By adding the new element at the right pointer to the frequency map and the running sum, the algorithm incrementally builds the window's state. This avoids recomputing sums from scratch and allows immediate detection of duplicates via the frequency map. This step is the forward expansion phase of the sliding window, preparing for validation and possible contraction.
Interview Quick-Check
Core Logic
Incrementing the count of the current element and adding it to the running sum maintains an accurate window state.
State & Boundaries
The right pointer moves forward one step per iteration, ensuring each element is processed exactly once in this phase.
Common Pitfalls & Bugs
Failing to update the frequency map or sum correctly leads to incorrect duplicate detection or sum calculation.
Shrink Window to Restore Validity When Constraints Break
| 15 | while count[n] > 1 or right - left + 1 > k: |
| 17 | left_val = nums[left] |
| 18 | count[left_val] -= 1 |
| 20 | if count[left_val] == 0: |
| 21 | del count[left_val] |
| 23 | curr_sum -= left_val |
| 24 | left += 1 |
Objective
To contract the window from the left while duplicates exist or the window size exceeds k, updating counts and sum to maintain correctness.
Key Insight
When the window contains duplicates or is too large, the algorithm must remove elements from the left to restore the distinctness and size constraints. Decrementing counts and removing keys when counts reach zero keeps the frequency map accurate. Adjusting the running sum by subtracting the removed element ensures the sum reflects the current window. This dynamic contraction is critical to maintaining a valid window and enabling efficient maximum sum updates.
Interview Quick-Check
Core Logic
The while loop condition ensures the window is shrunk until it contains only distinct elements and has size at most k.
State & Boundaries
Removing elements from the left pointer updates the window boundaries and state consistently.
Common Pitfalls & Bugs
Not deleting keys with zero count can cause incorrect duplicate detection; forgetting to update the sum leads to wrong maximum calculations.
Update Maximum Sum When Window Size Equals K
| 26 | if right - left + 1 == k: |
| 27 | best = max(best, curr_sum) |
Objective
To check if the current window size is exactly k and update the best sum found so far accordingly.
Key Insight
Only subarrays of size exactly k are valid candidates. When the window reaches this size, the algorithm compares the current sum to the best sum and updates if larger. This step ensures the final answer reflects the maximum sum of any valid subarray, leveraging the maintained running sum for O(1) updates.
Interview Quick-Check
Core Logic
Checking window size equality to k ensures only valid subarrays contribute to the maximum sum.
State & Boundaries
The window size is computed as right - left + 1, reflecting inclusive indices.
Common Pitfalls & Bugs
Updating the maximum sum only when the window size equals k prevents incorrect results from smaller or larger windows.
Return the Maximum Sum Found
| 29 | return best |
Objective
To return the maximum sum of a subarray of size k with distinct elements after processing the entire array.
Key Insight
After the sliding window has traversed the array, the best variable holds the maximum sum found. Returning this value completes the solution, providing the correct answer or zero if no valid subarray was found.
Interview Quick-Check
Core Logic
Returning the best sum after full traversal ensures the final answer reflects the global maximum.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while count[n] > 1 or right - left + 1 > k:While the window contains duplicates or exceeds size k, shrink it from the left.
This while loop is the core mechanism that maintains the sliding window's validity by removing elements until the window contains only distinct elements and its size does not exceed k.
best = max(best, curr_sum)Update the best sum if the current window's sum is greater.
This max operation is the critical step that tracks the best valid subarray sum, ensuring the algorithm returns the correct maximum.
count = {}Initialize a dictionary to count frequencies of elements in the current window.
This frequency map is essential for detecting duplicates efficiently, enabling O(1) average-time checks for element counts within the window.
count[n] = count.get(n, 0) + 1Increment the count of the current element in the frequency map.
Updating the count tracks how many times the element appears in the window, enabling duplicate detection.
count[left_val] -= 1Decrement the count of the left element in the frequency map.
Reducing the count reflects the removal of this element from the window, which may eliminate duplicates.
if count[left_val] == 0:Remove the element from the frequency map if its count reaches zero.
Deleting keys with zero count prevents stale entries that could falsely indicate duplicates, maintaining accurate state.
curr_sum -= left_valSubtract the left element's value from the running sum.
Updating the sum to reflect the removal maintains correctness of the window's total without recomputing.
if right - left + 1 == k:Check if the current window size equals k.
Only windows of size exactly k are valid candidates for the maximum sum calculation.
curr_sum = 0Initialize the running sum of elements in the current window.
Maintaining a running sum allows efficient updates of the window's total without recomputing sums from scratch.
curr_sum += nAdd the current element's value to the running sum.
Incrementally updating the sum maintains an accurate total for the current window efficiently.
del count[left_val]Delete the element key from the frequency map.
This explicit deletion ensures the frequency map only contains elements currently in the window, simplifying duplicate checks.
left += 1Move the left pointer forward to shrink the window.
Advancing the left pointer contracts the window, restoring validity and enabling further exploration.
best = 0Initialize the variable to track the maximum sum found.
This variable accumulates the best valid subarray sum encountered during the traversal.
for right in range(len(nums)):Iterate over the array with the right pointer expanding the window.
The right pointer moves forward to include new elements, enabling exploration of all possible subarrays.
left_val = nums[left]Retrieve the element at the left pointer to remove it from the window.
Identifying the element to remove is necessary to update counts and sum correctly during window contraction.
return bestReturn the maximum sum found after processing all subarrays.
Returning the accumulated best sum completes the solution, providing the final answer or zero if no valid subarray exists.
left = 0Initialize the left pointer of the sliding window.
The left pointer marks the start of the current window and moves forward to shrink the window when constraints are violated.
n = nums[right]Retrieve the current element at the right pointer.
This element is the candidate to add to the window, affecting counts and sum.
Test Your Understanding
Why must the window shrink when a duplicate is detected or the window size exceeds k?
Because the problem requires subarrays of size exactly k with all distinct elements, any duplicate or oversized window violates these constraints. Shrinking the window from the left removes duplicates or reduces size, restoring validity and enabling correct maximum sum calculation.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Maximum Sum of Distinct Subarrays With Length K from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Sum of Distinct Subarrays With Length K drill