You are given an integer array nums and two positive integers m and k.
Return the maximum sum out of all almost unique subarrays of length k of nums. If no such subarray exists, return 0.
A subarray of nums is almost unique if it contains at least m distinct elements.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,6,7,3,1,7], m = 3, k = 4
Output: 18
Explanation: There are 3 almost unique subarrays of size k = 4. These subarrays are [2, 6, 7, 3], [6, 7, 3, 1], and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3] which has a sum of 18.
Example 2:
Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3 Output: 23 Explanation: There are 5 almost unique subarrays of size k. These subarrays are [5, 9, 9], [9, 9, 2], [9, 2, 4], [2, 4, 5], and [4, 5, 4]. Among these subarrays, the one with the maximum sum is [5, 9, 9] which has a sum of 23.
Example 3:
Input: nums = [1,2,1,2,1,2,1], m = 3, k = 3 Output: 0 Explanation: There are no subarrays of sizek = 3that contain at leastm = 3distinct elements in the given array [1,2,1,2,1,2,1]. Therefore, no almost unique subarrays exist, and the maximum sum is 0.
Constraints:
1 <= nums.length <= 2 * 1041 <= m <= k <= nums.length1 <= nums[i] <= 109Problem Overview: You are given an integer array nums, a window size k, and a threshold m. Among all subarrays of length k, return the maximum possible sum where the subarray contains at least m distinct elements.
Approach 1: Brute Force with Optimization Check (O(n * k) time, O(k) space)
Iterate over every possible subarray of length k. For each starting index, compute the sum of the next k elements and track distinct values using a hash set or frequency map. If the number of unique elements is at least m, update the maximum sum. The optimization comes from stopping the distinct count early once the threshold is met, but the algorithm still scans up to k elements for each window. Time complexity is O(n * k) because each window requires up to k operations, and space complexity is O(k) to store element frequencies.
Approach 2: Sliding Window with HashMap (O(n) time, O(k) space)
This problem naturally fits a fixed-size sliding window. Maintain a window of size k while tracking the current sum and the frequency of elements in a HashMap. As you expand the window to the right, add the new element to the sum and update its frequency. When the window size exceeds k, remove the leftmost element, subtract it from the sum, and update its frequency (removing it from the map when the count reaches zero). The number of keys in the map represents the count of distinct elements. Each time the window size equals k, check whether the distinct count is at least m and update the maximum sum. Each element enters and leaves the window once, so the time complexity is O(n) and space complexity is O(k).
The sliding window approach works well because the window size never changes. Instead of recomputing sums and distinct counts from scratch, you update them incrementally when elements enter or leave the window. This reduces repeated work and turns a quadratic-style scan into a linear pass.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force method shows you understand the constraint of fixed-length subarrays, but the optimal approach demonstrates your ability to apply sliding window techniques with a hash table to maintain dynamic counts in an array. Linear-time solutions using incremental updates are a common expectation for medium-level array problems.
In this approach, we utilize the sliding window technique along with a hashmap to track the frequency of elements within the current subarray window. As we slide the window, we maintain the count of distinct elements and the sum of the subarray. This allows us to efficiently check if the current subarray is almost unique.
The C solution uses a frequency array to track occurrences of elements within the sliding window. If the window exceeds size k, we shrink it from the left. We check the distinct element count to ensure the 'almost unique' condition is met before calculating the sum.
Time Complexity: O(n) where n is the length of the array due to the sliding window mechanism.
Space Complexity: O(1) if we consider fixed maximum value range, otherwise O(m) where m is the number of unique integers in the range.
For this approach, a more straightforward brute force method generates all subarrays of length k. However, optimizing by early exit from impossible subarrays can reduce some checks. The 'almost unique' condition is verified for each subarray explicitly.
The Python brute force solution checks every possible subarray of length k from nums. It uses a set to track distinct elements, helping in validating the almost unique condition of each generated subarray for aggregation.
Time Complexity: O(n*k), where each subarray is evaluated for sum and distinctness.
Space Complexity: O(k) due to the use of sets for maintaining distinct numbers.
We can traverse the array nums, maintain a window of size k, use a hash table cnt to count the occurrence of each element in the window, and use a variable s to sum all elements in the window. If the number of different elements in cnt is greater than or equal to m, then we update the answer ans = max(ans, s).
After the traversal ends, return the answer.
The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Sliding Window with HashMap | Time Complexity: O(n) where n is the length of the array due to the sliding window mechanism. |
| Brute Force with Optimization Check | Time Complexity: O(n*k), where each subarray is evaluated for sum and distinctness. |
| Sliding Window + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Optimization Check | O(n * k) | O(k) | Useful for understanding the problem or when constraints are small |
| Sliding Window with HashMap | O(n) | O(k) | Best general solution for large arrays and interview settings |
Leetcode BiWeekly contest 112 - Medium - Maximum Sum of Almost Unique Subarray • Prakhar Agrawal • 950 views views
Watch 9 more video solutions →Practice Maximum Sum of Almost Unique Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor