2461. Maximum Sum of Distinct Subarrays With Length K

2461. Maximum Sum of Distinct Subarrays With Length K

Difficulty: Medium

Topics: Array, Hash Table, Sliding Window

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 <= 105


• 1 <= nums[i] <= 105

Hint:

1. Which elements change when moving from the subarray of size k that ends at index i to the subarray of size k that ends at index i + 1?


2. Only two elements change, the element at i + 1 is added into the subarray, and the element at i - k + 1 gets removed from the subarray.


3. Iterate through each subarray of size k and keep track of the sum of the subarray and the frequency of each element.

Solution:

We can follow these steps:

Approach:

1. 
   Sliding Window: The window size is k, and we slide the window through the array while maintaining the sum of the current window and checking if all elements in the window are distinct.


2. 
   Hash Table (or associative array): Use an associative array (hash table) to track the frequency of elements in the current window. If any element appears more than once, the window is invalid.


3. 
   Updating the Window: As we slide the window, add the new element (i.e., the element coming into the window), and remove the old element (i.e., the element leaving the window). Update the sum accordingly and check if the window is valid (i.e., all elements are distinct).


4. 
   Return the Maximum Sum: We need to keep track of the maximum sum encountered among valid subarrays.

Algorithm:

1. Initialize a hash table freq to store the frequency of elements in the current window.


2. Start by calculating the sum for the first window of size k and store the result if the window contains distinct elements.


3. Slide the window from left to right by:
   
   
   
   
   • Removing the element that leaves the window from the left.
   
   
   • Adding the element that enters the window from the right.
   
   
   • Update the sum and the hash table, and check if the window still contains only distinct elements.
   
   
   
   


4. If the window has valid distinct elements, update the maximum sum.


5. If no valid subarray is found, return 0.

Let's implement this solution in PHP: a star on GitHub or sharing the post on your favorite social networks 😍.