Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5

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.

Solution

Method 1 - Sliding window

Here is the approach:

  1. Initial Setup:
    • We need to find subarrays of length k where all the elements are distinct.
    • Initialize ans to store the result (maximum subarray sum), currentSum to keep the sum of the current window, and window as a map to count the frequency of elements within the current window.
  2. Form the Initial Window:
    • Loop through the first k elements of the nums array.
    • Add each element to the window map and update currentSum by adding the element’s value.
    • After the loop, check if the size of the window (distinct elements) equals k:
      • If true, set ans to currentSum as the initial valid subarray sum.
  3. Sliding Window Technique for the Rest of the Elements:
    • Continue the loop for the rest of the array starting from index k.
    • For each new element, add it to the window and increment its frequency.
    • Remove the element that slides out from the left of the window by decrementing its frequency in the window:
      • If its frequency becomes zero, remove the element from the window.
    • Update currentSum by adding the new element and subtracting the element that slid out.
    • Check if the size of the window (distinct elements) equals k:
      • If true, update ans with the maximum value between the current ans and currentSum.
  4. Return the Final Result:
    • Return ans which holds the maximum subarray sum meeting the conditions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long ans = 0, currentSum = 0;
        Map<Integer, Integer> window = new HashMap<>();
        int i = 0;
        
        // Store first k elements in the map
        while (i < k && i < nums.length) {
            window.put(nums[i], window.getOrDefault(nums[i], 0) + 1);
            currentSum += nums[i];
            i++;
        }
        
        if (window.size() == k) ans = currentSum; // if all distinct, then ans = sum
        
        // Process the rest of the elements
        while (i < nums.length) {
            window.put(nums[i], window.getOrDefault(nums[i], 0) + 1);
            window.put(nums[i - k], window.get(nums[i - k]) - 1);
            if (window.get(nums[i - k]) == 0) window.remove(nums[i - k]);
            
            currentSum += nums[i];
            currentSum -= nums[i - k];
            if (window.size() == k) ans = Math.max(ans, currentSum);
            i++;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        ans: int = 0
        current_sum: int = 0
        window = defaultdict(int)
        i = 0
        
        # Store first k elements in the map
        while i < k and i < len(nums):
            window[nums[i]] += 1
            current_sum += nums[i]
            i += 1
        
        if len(window) == k:
            ans = current_sum
        
        # Process the rest of the elements
        while i < len(nums):
            window[nums[i]] += 1
            window[nums[i - k]] -= 1
            if window[nums[i - k]] == 0:
                del window[nums[i - k]]
            
            current_sum += nums[i]
            current_sum -= nums[i - k]
            if len(window) == k:
                ans = max(ans, current_sum)
            i += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array. Each element is processed a constant number of times (added and removed from the map).
  • 🧺 Space complexity: O(k), used for storing elements in the window map.