Maximum Sum of distinct Subarrays of length K

XXX. Maximum Subarray Sum with Distinct Elements

Sliding Window

Hash Map

Problem Statement:

Given an array nums and an integer k, find the maximum sum of any subarray of length k such that all elements in the subarray are distinct.

Algorithm:

1. Initialize two pointers, i and j, to represent the sliding window boundaries.
2. Create a hash map to store the frequency of elements currently in the window and a variable to track the current sum.
3. Expand the window by moving the right pointer j:
• Add the current element to the sum and update its count in the hash map.
• If the window size exceeds k or the number of distinct elements exceeds k, shrink the window by moving the left pointer i:
• Remove the leftmost element from the sum and decrement its count in the hash map.
• Remove the element from the hash map if its count becomes zero.
4. If the window size is exactly k and all elements are distinct, update the maximum sum.
5. Continue until the right pointer reaches the end of the array.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is added and removed from the hash map at most once.
Space Complexity: O(k), for the hash map storing up to k elements.

Java Implementation:

import java.util.*;

public class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int i = 0, j = 0;
        Map map = new HashMap<>();
        long sum = 0;
        long max = 0; 

        while (j < nums.length) {
            // Add the current element to the sum and update its count
            sum += nums[j];
            map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
            
            // Shrink the window if necessary
            while (j - i + 1 > k || map.size() > k) {
                sum -= nums[i];
                map.put(nums[i], map.getOrDefault(nums[i], 0) - 1);
                if (map.get(nums[i]) == 0) map.remove(nums[i]);
                i++;
            }

            // Update the maximum sum if the window is valid
            if (j - i + 1 == k && map.size() == k) 
                max = Math.max(max, sum);
            
            // Expand the window
            j++;
        }
        return max;
    }
}