Problem

You are given an integer array nums and two positive integers m and k.

Return _themaximum 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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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 * 10^4
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Sliding Window with Hash Map

Intuition

To find the maximum sum of a subarray of length k with at least m distinct elements, we can use a sliding window. By maintaining a count of each element in the window, we can efficiently check the number of distinct elements and update the sum as the window moves.

Approach

  1. Use a hash map to count occurrences of elements in the current window.
  2. Initialize the window with the first k elements, tracking the sum and distinct count.
  3. For each window position:
    • If the window has at least m distinct elements, update the maximum sum.
    • Slide the window by removing the leftmost element and adding the next element, updating the hash map and sum accordingly.
  4. Return the maximum sum found, or 0 if no valid subarray exists.

Complexity

  • ⏰ Time complexity: O(n) — Each element is added and removed from the window once.
  • 🧺 Space complexity: O(k) — Hash map stores up to k elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maxSum(vector<int>& nums, int m, int k) {
        unordered_map<int, int> cnt;
        int sum = 0, ans = 0, n = nums.size();
        for (int i = 0; i < k; ++i) {
            cnt[nums[i]]++;
            sum += nums[i];
        }
        if (cnt.size() >= m) ans = sum;
        for (int i = k; i < n; ++i) {
            cnt[nums[i-k]]--;
            if (cnt[nums[i-k]] == 0) cnt.erase(nums[i-k]);
            sum -= nums[i-k];
            cnt[nums[i]]++;
            sum += nums[i];
            if (cnt.size() >= m) ans = max(ans, sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maxSum(nums []int, m, k int) int {
    cnt := map[int]int{}
    sum, ans := 0, 0
    for i := 0; i < k; i++ {
        cnt[nums[i]]++
        sum += nums[i]
    }
    if len(cnt) >= m { ans = sum }
    for i := k; i < len(nums); i++ {
        cnt[nums[i-k]]--
        if cnt[nums[i-k]] == 0 { delete(cnt, nums[i-k]) }
        sum -= nums[i-k]
        cnt[nums[i]]++
        sum += nums[i]
        if len(cnt) >= m && sum > ans { ans = sum }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxSum(int[] nums, int m, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int sum = 0, ans = 0;
        for (int i = 0; i < k; ++i) {
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            sum += nums[i];
        }
        if (cnt.size() >= m) ans = sum;
        for (int i = k; i < nums.length; ++i) {
            cnt.put(nums[i-k], cnt.get(nums[i-k]) - 1);
            if (cnt.get(nums[i-k]) == 0) cnt.remove(nums[i-k]);
            sum -= nums[i-k];
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            sum += nums[i];
            if (cnt.size() >= m) ans = Math.max(ans, sum);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maxSum(nums: IntArray, m: Int, k: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        var sum = 0
        var ans = 0
        for (i in 0 until k) {
            cnt[nums[i]] = cnt.getOrDefault(nums[i], 0) + 1
            sum += nums[i]
        }
        if (cnt.size >= m) ans = sum
        for (i in k until nums.size) {
            cnt[nums[i-k]] = cnt[nums[i-k]]!! - 1
            if (cnt[nums[i-k]] == 0) cnt.remove(nums[i-k])
            sum -= nums[i-k]
            cnt[nums[i]] = cnt.getOrDefault(nums[i], 0) + 1
            sum += nums[i]
            if (cnt.size >= m) ans = maxOf(ans, sum)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def max_sum(nums: list[int], m: int, k: int) -> int:
    from collections import defaultdict
    cnt: dict[int, int] = defaultdict(int)
    sum_ = 0
    ans = 0
    for i in range(k):
        cnt[nums[i]] += 1
        sum_ += nums[i]
    if len(cnt) >= m:
        ans = sum_
    for i in range(k, len(nums)):
        cnt[nums[i-k]] -= 1
        if cnt[nums[i-k]] == 0:
            del cnt[nums[i-k]]
        sum_ -= nums[i-k]
        cnt[nums[i]] += 1
        sum_ += nums[i]
        if len(cnt) >= m:
            ans = max(ans, sum_)
    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

impl Solution {
    pub fn max_sum(nums: Vec<i32>, m: i32, k: i32) -> i32 {
        use std::collections::HashMap;
        let (m, k) = (m as usize, k as usize);
        let mut cnt = HashMap::new();
        let mut sum = 0;
        let mut ans = 0;
        for i in 0..k {
            *cnt.entry(nums[i]).or_insert(0) += 1;
            sum += nums[i];
        }
        if cnt.len() >= m { ans = sum; }
        for i in k..nums.len() {
            let out = nums[i-k];
            let entry = cnt.get_mut(&out).unwrap();
            *entry -= 1;
            if *entry == 0 { cnt.remove(&out); }
            sum -= out;
            *cnt.entry(nums[i]).or_insert(0) += 1;
            sum += nums[i];
            if cnt.len() >= m && sum > ans { ans = sum; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxSum(nums: number[], m: number, k: number): number {
        const cnt = new Map<number, number>();
        let sum = 0, ans = 0;
        for (let i = 0; i < k; ++i) {
            cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
            sum += nums[i];
        }
        if (cnt.size >= m) ans = sum;
        for (let i = k; i < nums.length; ++i) {
            cnt.set(nums[i-k], cnt.get(nums[i-k])! - 1);
            if (cnt.get(nums[i-k]) === 0) cnt.delete(nums[i-k]);
            sum -= nums[i-k];
            cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
            sum += nums[i];
            if (cnt.size >= m) ans = Math.max(ans, sum);
        }
        return ans;
    }
}