Maximum Sum of Almost Unique Subarray - Video Solutions
Leetcode BiWeekly contest 112 - Medium - Maximum Sum of Almost Unique Subarray
Maximum Sum of Almost Unique Subarray - Video Solution
Watch 10 video solutions for Maximum Sum of Almost Unique Subarray, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Prakhar Agrawal has 963 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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] <= 109
Approach Overview
Problem 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.
Complexity Analysis
| 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 |