# Maximum Sum of Distinct Subarrays With Length K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-distinct-subarrays-with-length-k
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## 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._

**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`

# Approaches
## Brute Force Iteration
This approach involves iterating through every possible subarray of length `k`, checking if it contains distinct elements, and if so, calculating its sum. The maximum sum found is then returned.
**Time:** O(n * k) - The outer loop runs `n-k+1` times, and for each iteration, the inner loop runs `k` times. This results in a quadratic time complexity relative to the input size and `k`. · **Space:** O(k) - In each iteration of the outer loop, a `HashSet` is created which can store up to `k` elements.
**Pros:** Simple to understand and implement.; Directly translates the problem statement into code.
**Cons:** Highly inefficient, with a time complexity of O(n*k), which will be too slow for large inputs.; Performs a lot of redundant work. For each subarray, it re-calculates the sum and re-checks for distinct elements from scratch, even for overlapping parts.
### Explanation
The logic is to check every single subarray of length `k`. We can use a nested loop structure. The outer loop defines the starting point of the subarray, and the inner loop iterates through the `k` elements of that subarray.

To check for uniqueness within the `k` elements, a `HashSet` is an effective tool. For each subarray, we create a new `HashSet`. As we iterate through its elements, we add them to the set and also accumulate their sum. If we try to add an element that's already present in the set, we know the subarray has duplicates. In this case, we can immediately discard this subarray and move to the next one.

If the inner loop completes without finding any duplicates, it means all `k` elements are distinct. We then compare its sum with the maximum sum found so far and update it if necessary. This process is repeated for all `n-k+1` possible subarrays.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long maxSum = 0;
        int n = nums.length;
        for (int i = 0; i <= n - k; i++) {
            Set<Integer> distinctElements = new HashSet<>();
            long currentSum = 0;
            boolean hasDuplicates = false;
            // Check the subarray nums[i...i+k-1]
            for (int j = i; j < i + k; j++) {
                if (!distinctElements.add(nums[j])) {
                    hasDuplicates = true;
                    break;
                }
                currentSum += nums[j];
            }
            
            if (!hasDuplicates) {
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a variable `maxSum` to 0.
- Iterate through the array `nums` with an index `i` from `0` to `n-k`, where `n` is the length of `nums`. This loop defines the starting position of each subarray.
- For each `i`, create a new `HashSet` to store the elements of the current subarray and a `currentSum` variable initialized to 0.
- Start an inner loop with index `j` from `i` to `i + k - 1`.
- Inside the inner loop, check if `nums[j]` can be added to the `HashSet`. The `add` method returns `false` if the element is already present.
- If a duplicate is found, this subarray is invalid. Stop processing it and move to the next starting position `i`.
- If the element is unique, add it to the set and add its value to `currentSum`.
- After the inner loop finishes, if no duplicates were found (i.e., the loop completed for all `k` elements), the subarray is valid. Compare `currentSum` with `maxSum` and update `maxSum` if `currentSum` is larger.
- After the outer loop completes, return `maxSum`.

## Sliding Window with Frequency Map
This approach uses a sliding window of size `k` to efficiently calculate the sum and check for distinct elements. By sliding the window one element at a time, we can update the sum and element counts in constant time on average, avoiding recalculation.
**Time:** O(n) - We iterate through the array a single time. All operations within the loop (map updates, arithmetic) take constant time on average. · **Space:** O(k) - The `HashMap` stores at most `k` key-value pairs, corresponding to the elements in the current window.
**Pros:** Highly efficient with O(n) time complexity, making it suitable for large inputs.; Optimal solution for the given constraints.
**Cons:** Slightly more complex to implement compared to the brute-force approach.; Requires extra space for the frequency map, which could be O(k).
### Explanation
This optimized approach avoids the redundant work of the brute-force method by using a sliding window. The window is a conceptual frame of size `k` that moves across the array one element at a time. We maintain the sum of elements and their frequencies within the current window.

We use a `HashMap` to store the frequency of each number in the window. A key property we use is that a window of `k` elements has all distinct numbers if and only if the number of unique keys in our frequency map is exactly `k`.

The process begins by iterating through the array. For each element, we add it to our window. Once the window reaches size `k`, we check if it's a valid subarray. Then, for all subsequent elements, we "slide" the window by:
1. Adding the new element from the right to our sum and frequency map.
2. Removing the leftmost element (which is now outside the window) from our sum and frequency map.

After each slide, we check if the map's size is `k`. If it is, we have a valid subarray, and we update our maximum sum. This way, each element of the input array is processed only a constant number of times, leading to a linear time complexity.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long maxSum = 0;
        long currentSum = 0;
        Map<Integer, Integer> freqMap = new HashMap<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // Add the current element to the window
            currentSum += nums[i];
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);

            // If window size is now greater than k, remove the leftmost element
            if (i >= k) {
                int leftElement = nums[i - k];
                currentSum -= leftElement;
                freqMap.put(leftElement, freqMap.get(leftElement) - 1);
                if (freqMap.get(leftElement) == 0) {
                    freqMap.remove(leftElement);
                }
            }

            // Check if the current window is valid (size k and all distinct)
            if (i >= k - 1) {
                if (freqMap.size() == k) {
                    maxSum = Math.max(maxSum, currentSum);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize `maxSum = 0L`, `currentSum = 0L`, and a `HashMap<Integer, Integer> freqMap` to store element frequencies in the current window.
- Iterate through the `nums` array with index `i` from `0` to `n-1`.
- **Add element to window:** Add `nums[i]` to `currentSum` and increment its count in `freqMap`.
- **Maintain window size:** If `i >= k`, the window is now of size `k+1`. We must remove the leftmost element, `nums[i-k]`, to shrink it back to size `k`.
  - Subtract `nums[i-k]` from `currentSum`.
  - Decrement the count of `nums[i-k]` in `freqMap`.
  - If the count of `nums[i-k]` becomes 0, remove it from the map to keep the map size accurate for the distinctness check.
- **Check for valid subarray:** If the window has reached size `k` (i.e., `i >= k-1`), check if it meets the distinctness condition.
  - The condition is met if `freqMap.size() == k`.
  - If it is met, update `maxSum = Math.max(maxSum, currentSum)`.
- After the loop finishes, return `maxSum`.

# Solutions
### CSharp

```csharp
public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        int n = nums.Length;
        Dictionary < int, int > cnt = new Dictionary < int, int > (k);
        long s = 0;
        for (int i = 0; i < k; ++i) {
            if (!cnt.ContainsKey(nums[i])) {
                cnt[nums[i]] = 1;
            } else {
                cnt[nums[i]]++;
            }
            s += nums[i];
        }
        long ans = cnt.Count == k ? s : 0;
        for (int i = k; i < n; ++i) {
            if (!cnt.ContainsKey(nums[i])) {
                cnt[nums[i]] = 1;
            } else {
                cnt[nums[i]]++;
            }
            if (--cnt[nums[i - k]] == 0) {
                cnt.Remove(nums[i - k]);
            }
            s += nums[i] - nums[i - k];
            if (cnt.Count == k) {
                ans = Math.Max(ans, s);
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  long maximumSubarraySum(int[] nums, int k) {
    int n = nums.length;
    Map<Integer, Integer> cnt = new HashMap<>(k);
    long s = 0;
    for (int i = 0; i < k; ++i) {
      cnt.merge(nums[i], 1, Integer : : sum);
      s += nums[i];
    }
    long ans = cnt.size() == k ? s : 0;
    for (int i = k; i < n; ++i) {
      cnt.merge(nums[i], 1, Integer : : sum);
      s += nums[i];
      if (cnt.merge(nums[i - k], -1, Integer : : sum) == 0) {
        cnt.remove(nums[i - k]);
      }
      s -= nums[i - k];
      if (cnt.size() == k) {
        ans = Math.max(ans, s);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSubarraySum(vector<int> &nums, int k) {
    using ll = long long;
    int n = nums.size();
    unordered_map<int, ll> cnt;
    ll s = 0;
    for (int i = 0; i < k; ++i) {
      cnt[nums[i]]++;
      s += nums[i];
    }
    ll ans = cnt.size() == k ? s : 0;
    for (int i = k; i < n; ++i) {
      cnt[nums[i]]++;
      s += nums[i];
      cnt[nums[i - k]]--;
      s -= nums[i - k];
      if (cnt[nums[i - k]] == 0) {
        cnt.erase(nums[i - k]);
      }
      if (cnt.size() == k) {
        ans = max(ans, s);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int: cnt = Counter(nums[: k]) s = sum(nums[: k]) ans = s if len(cnt) == k else 0 for i in range(k, len(nums)): cnt[nums[i]] += 1 s += nums[i] cnt[nums[i - k]] -= 1 s -= nums[i - k] if cnt[nums[i - k]] == 0: del cnt[nums[i - k]] if len(cnt) == k: ans = max(ans, s) return ans

```