Maximum Sum of Distinct Subarrays With Length K - Video Solutions

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.