Maximum Sum of Distinct Subarrays With Length K - Solution & Explanation
Problem Statement
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:
- The length of the subarray is
k, and - All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,5,4,2,9,9,9], k = 3 Output: 15 Explanation: The subarrays of nums with length 3 are: - [1,5,4] which meets the requirements and has a sum of 10. - [5,4,2] which meets the requirements and has a sum of 11. - [4,2,9] which meets the requirements and has a sum of 15. - [2,9,9] which does not meet the requirements because the element 9 is repeated. - [9,9,9] which does not meet the requirements because the element 9 is repeated. We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions
Example 2:
Input: nums = [4,4,4], k = 3 Output: 0 Explanation: The subarrays of nums with length 3 are: - [4,4,4] which does not meet the requirements because the element 4 is repeated. We return 0 because no subarrays meet the conditions.
Constraints:
1 <= k <= nums.length <= 1051 <= nums[i] <= 105
Approach Overview
Problem Overview: Given an integer array and an integer k, find the maximum sum of any subarray of length k where all elements are distinct. If no such subarray exists, return 0. The challenge is enforcing both constraints simultaneously: fixed window size and uniqueness of elements.
Approach 1: Sorting (O(n log n) time, O(n) space)
This approach evaluates every subarray of length k, stores the elements temporarily, and checks if all values are distinct by sorting or using a set. Sorting a window allows you to quickly detect duplicates because equal elements become adjacent. After confirming uniqueness, compute the sum and track the maximum. While straightforward, this method repeatedly sorts windows, making the complexity O(n log k) per window in practice (commonly simplified to O(n log n)). This is mostly useful as a conceptual or brute-force baseline before introducing optimized techniques.
Approach 2: Hash Map for Counting (Sliding Window) (O(n) time, O(k) space)
The optimal solution uses a sliding window combined with a hash table to maintain frequency counts of elements in the current window. Expand the window by moving the right pointer and update the running sum. Each time the window size exceeds k, remove the leftmost element, decrement its count in the hash map, and update the sum. The key condition is checking whether the window contains exactly k distinct elements. When the window length is k and the map size is also k, every element is unique, so the current sum becomes a candidate for the maximum.
This technique avoids recomputing sums or rechecking duplicates from scratch. Every element enters and leaves the window once, giving linear time complexity. The hash map ensures constant-time frequency updates and uniqueness checks. Because the window size never exceeds k, the extra memory stays bounded by O(k). This pattern appears frequently in array problems involving fixed-length windows and uniqueness constraints.
Recommended for interviews: Interviewers expect the sliding window + hash map solution. Starting with the naive window check shows you understand the problem constraints, but optimizing it to a linear-time sliding window demonstrates strong algorithmic thinking and familiarity with common array patterns.
Approach 1: Approach 1: Hash Map for Counting
This approach uses a hash map (or dictionary) to count occurrences of elements in the data. By iterating through the data once to populate the hash map, we can achieve efficient lookups. The main idea is to traverse the input list, counting occurrences of each element, and storing these counts in a hash map for quick access in the future.
This C program sets up an array to count the frequency of each element in a list. It assumes input values are non-negative and less than MAX. We use a simple array count to store the tally of each integer that appears in the input list.
Complexity
Time Complexity: O(n) for traversing the list once.
Space Complexity: O(k), where k is the range of input values (determined by MAX).
Approach 2: Approach 2: Sorting
By sorting the input list, elements of the same value will be grouped together. We can then iterate through the sorted list to count the occurrences of each element. This takes advantage of the property of sorting to simplify the counting process.
This C program sorts the list of elements using qsort(), then iterates over the sorted list to count consecutive occurrences of each number. It outputs the frequency of each unique element.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space for counting.
Approach 3: Sliding Window + Hash Table
We maintain a sliding window of length k, use a hash table cnt to record the count of each number in the window, and use a variable s to record the sum of all numbers in the window. Each time we slide the window, if all numbers in the window are unique, we update the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map for Counting | Time Complexity: O(n) for traversing the list once. |
| Approach 2: Sorting | Time Complexity: O(n log n) due to sorting. |
| Sliding Window + Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting each window | O(n log k) | O(k) | Simple baseline approach when optimizing is not required or for understanding the problem first |
| Hash Map + Sliding Window | O(n) | O(k) | Best general solution for large arrays where you must maintain a fixed window and enforce distinct elements |
Video Solution
Maximum Sum of Distinct Subarrays With Length K - Leetcode 2461 - Python • NeetCodeIO • 19,761 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Sum of Distinct Subarrays With Length K easy or hard?
Maximum Sum of Distinct Subarrays With Length K Python/Java solution
How to solve Maximum Sum of Distinct Subarrays With Length K in O(n)?
What is the best approach for Maximum Sum of Distinct Subarrays With Length K?
Is Maximum Sum of Distinct Subarrays With Length K asked at Google/Amazon/Meta?
What data structure is used in Maximum Sum of Distinct Subarrays With Length K?
What is the time complexity of Maximum Sum of Distinct Subarrays With Length K?
Ready to solve this problem?
Practice Maximum Sum of Distinct Subarrays With Length K with our built-in code editor and test cases.
Practice on FleetCode