Maximum Sum of Almost Unique Subarray - Video Solutions

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.