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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To iterate through the array, expanding the window by moving the right pointer, updating element counts and the current sum accordingly.
Shrink Window to Restore Validity When Constraints Break
To contract the window from the left while duplicates exist or the window size exceeds k, updating counts and sum to maintain correctness.
Update Maximum Sum When Window Size Equals K
To check if the current window size is exactly k and update the best sum found so far accordingly.
Return the Maximum Sum Found
To return the maximum sum of a subarray of size k with distinct elements after processing the entire array.
4 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why must the window shrink when a duplicate is detected or the window size exceeds k?
See the answer with Pro.
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