# Maximum Sum of Almost Unique Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-of-almost-unique-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-almost-unique-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums` and two positive integers `m` and `k`.

Return _the **maximum sum** out of all **almost unique** subarrays of length_ `k` _of_ `nums`. If no such subarray exists, return `0`.

A subarray of `nums` is **almost unique** if it contains at least `m` distinct elements.

A subarray is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** nums = [2,6,7,3,1,7], m = 3, k = 4
**Output:** 18
**Explanation:** There are 3 almost unique subarrays of size `k = 4`. These subarrays are [2, 6, 7, 3], [6, 7, 3, 1], and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3] which has a sum of 18.

**Example 2:**

**Input:** nums = [5,9,9,2,4,5,4], m = 1, k = 3
**Output:** 23
**Explanation:** There are 5 almost unique subarrays of size k. These subarrays are [5, 9, 9], [9, 9, 2], [9, 2, 4], [2, 4, 5], and [4, 5, 4]. Among these subarrays, the one with the maximum sum is [5, 9, 9] which has a sum of 23.

**Example 3:**

**Input:** nums = [1,2,1,2,1,2,1], m = 3, k = 3
**Output:** 0
**Explanation:** There are no subarrays of size `k = 3` that contain at least `m = 3` distinct elements in the given array [1,2,1,2,1,2,1]. Therefore, no almost unique subarrays exist, and the maximum sum is 0.

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `1 <= m <= k <= nums.length`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible subarrays of length `k`. For each subarray, we check if it meets the 'almost unique' criteria (at least `m` distinct elements) and, if so, calculate its sum. We keep track of the maximum sum found across all valid subarrays.
**Time:** O(n * k), where `n` is the length of `nums`. The outer loop runs `n-k+1` times, and for each iteration, we loop `k` times to build the set and calculate the sum. This results in a quadratic time complexity in the worst case (when `k` is proportional to `n`). · **Space:** O(k), as we use a `HashSet` to store up to `k` elements for each subarray.
**Pros:** Simple to conceptualize and implement.; Correct for all cases, though not efficient.
**Cons:** Highly inefficient due to redundant calculations.; The time complexity of O(n*k) will lead to a 'Time Limit Exceeded' (TLE) error on larger test cases.
### Explanation
The brute-force method systematically examines every contiguous subarray of the specified length `k`.
- We use a loop that starts from the first element and ends at the last possible starting position for a subarray of length `k` (`nums.length - k`).
- Inside this loop, for each starting position `i`, we form a subarray `nums[i...i+k-1]`.
- To determine if this subarray is 'almost unique', we use a `HashSet`. We populate the set with the elements of the current subarray. The size of the `HashSet` gives us the count of distinct elements.
- If the count of distinct elements is `m` or more, we proceed to calculate the sum of the elements in this subarray.
- This sum is then compared with a running maximum, which is updated if the current sum is greater.
- After checking all possible subarrays, the final maximum sum is returned. If no 'almost unique' subarray is found, the initial maximum sum of 0 is returned.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long maximumSubarraySum(int[] nums, int m, int k) {
        long maxSum = 0;
        int n = nums.length;

        if (k > n) {
            return 0;
        }

        for (int i = 0; i <= n - k; i++) {
            Set<Integer> distinctElements = new HashSet<>();
            long currentSum = 0;
            
            // Consider subarray nums[i...i+k-1]
            for (int j = i; j < i + k; j++) {
                distinctElements.add(nums[j]);
                currentSum += nums[j];
            }

            // Check if the subarray is almost unique
            if (distinctElements.size() >= m) {
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}
```
### Algorithm
1. Initialize `maxSum` to 0.
2. Iterate through the array `nums` from index `i = 0` to `n - k`.
3. For each `i`, create a new `HashSet` and initialize `currentSum` to 0.
4. Create a subarray of length `k` starting at `i`.
5. Iterate through this subarray (from `j = i` to `i + k - 1`):
    a. Add `nums[j]` to the `HashSet`.
    b. Add `nums[j]` to `currentSum`.
6. After iterating through the subarray, check if the size of the `HashSet` is greater than or equal to `m`.
7. If it is, update `maxSum = Math.max(maxSum, currentSum)`.
8. After the outer loop finishes, return `maxSum`.

## Sliding Window with Frequency Map
A more efficient approach is to use a sliding window of size `k`. Instead of re-calculating the sum and distinct elements for each subarray, we maintain these values as the window slides across the array. We add the new element entering the window and remove the element leaving it, updating the sum and the count of distinct elements in constant time on average.
**Time:** O(n), where `n` is the length of `nums`. We iterate through the array once. The HashMap operations (get, put, remove) take O(1) on average. · **Space:** O(k), as the `HashMap` stores at most `k` distinct elements from the window.
**Pros:** Optimal time complexity of O(n).; Efficiently reuses calculations from the previous window.; Passes all test cases within the time limit.
**Cons:** Slightly more complex to implement due to managing the sliding window state (sum and frequency map).
### Explanation
This optimized method avoids the repeated work of the brute-force approach by using a sliding window.
- We maintain a window of size `k` and a `HashMap` to store the frequency of each number within that window. The size of the `HashMap` directly tells us the number of distinct elements.
- We also keep a running sum of the elements in the window.
- First, we initialize the window with the first `k` elements of the array. We calculate their sum and populate the frequency map. We check if this initial window is 'almost unique' and update our maximum sum if it is.
- Then, we iterate from the `k`-th element to the end of the array. In each step, we 'slide' the window one position to the right:
    1.  **Add new element**: The element at the right end of the new window (`nums[i]`) is added. We update the sum and its frequency in the map.
    2.  **Remove old element**: The element that just left the window from the left end (`nums[i-k]`) is removed. We update the sum and its frequency. If its frequency becomes zero, we remove the element from the map entirely to keep the map's size accurate for the distinct count.
- After each slide, we check if the number of distinct elements (the map's size) is at least `m`. If it is, we compare the current window's sum with our overall maximum sum and update it if necessary.
- This process continues until the window has passed over the entire array.
```java
import java.util.HashMap;
import java.util.Map;

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

        // Initialize the first window
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }

        // Check the first window
        if (freqMap.size() >= m) {
            maxSum = currentSum;
        }

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

            // Remove the element that is leaving the window
            int oldElement = nums[i - k];
            currentSum -= oldElement;
            freqMap.put(oldElement, freqMap.get(oldElement) - 1);
            if (freqMap.get(oldElement) == 0) {
                freqMap.remove(oldElement);
            }

            // Check if the current window is almost unique
            if (freqMap.size() >= m) {
                maxSum = Math.max(maxSum, currentSum);
            }
        }

        return maxSum;
    }
}
```
### Algorithm
1. Initialize `maxSum = 0`, `currentSum = 0`, and a `HashMap` called `freqMap` to store element frequencies.
2. Create the initial window of the first `k` elements:
    a. Iterate from `i = 0` to `k-1`.
    b. Add `nums[i]` to `currentSum`.
    c. Update the frequency of `nums[i]` in `freqMap`.
3. Check if the initial window is 'almost unique' (`freqMap.size() >= m`). If so, set `maxSum = currentSum`.
4. Slide the window across the rest of the array, from `i = k` to `n-1`:
    a. **Add** the new element `nums[i]` to the window: `currentSum += nums[i]` and update its count in `freqMap`.
    b. **Remove** the leftmost element `nums[i-k]` from the window: `currentSum -= nums[i-k]` and decrement its count in `freqMap`.
    c. If the count of `nums[i-k]` becomes 0 after decrementing, remove it from `freqMap`.
    d. Check if the current window is 'almost unique' (`freqMap.size() >= m`). If so, update `maxSum = Math.max(maxSum, currentSum)`.
5. Return `maxSum`.

# Solutions
### CSharp

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

### Java

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

```

### CPP

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

```

### Python

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

```