#2841

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Sum of Almost Unique Subarray

Find the maximum sum of subarrays that contain at least m distinct elements using array scanning and hash lookups efficiently.

array hash table sliding window

Problem Statement

Given an integer array nums and two positive integers m and k, identify subarrays of length k that contain at least m distinct elements. Return the maximum sum among all such subarrays. If no subarray meets the criteria, return 0.

A subarray is considered almost unique if it contains at least m distinct values. Examples include scanning arrays with overlapping windows and using a hash table to count distinct elements for each window to determine validity and sum efficiently.

Examples

Example 1

Input: nums = [2,6,7,3,1,7], m = 3, k = 4

Output: 18

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

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

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

Solution Approach

Sliding Window with Hash Map

Maintain a sliding window of length k while using a hash map to count occurrences of each number. Incrementally add the new element and remove the outgoing element while updating distinct counts to check the almost unique condition.

Sum Tracking

Keep a running sum of the current window. Only consider updating the maximum sum when the number of distinct elements meets or exceeds m. This ensures we avoid unnecessary recomputation and maintain efficiency.

Edge Case Handling

Handle cases where no subarray has enough distinct elements by returning 0. Also ensure proper updates to the hash map when duplicate elements enter or leave the window to maintain correct distinct counts.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each element is added and removed from the window once. Space complexity is O(k) due to the hash map storing counts of elements in the current window.

What Interviewers Usually Probe

Using a hash map or set to track distinct elements in the sliding window.
Ensuring incremental updates of sum and distinct count instead of recomputing from scratch.
Handling cases where subarrays do not meet the m distinct elements requirement.

Common Pitfalls or Variants

Common pitfalls

Recomputing the sum or distinct count for every window instead of updating incrementally.
Failing to correctly decrement counts in the hash map when elements leave the window.
Not accounting for the case where no almost unique subarray exists and returning an incorrect value.

Follow-up variants

Change the distinct element threshold m to vary the almost uniqueness constraint.
Use a larger k relative to the array size to test sliding window efficiency under near-full coverage.
Optimize for streaming arrays where elements arrive one by one instead of a static array.

FAQ

What is an almost unique subarray in this problem?

An almost unique subarray is a subarray of length k that contains at least m distinct elements in the given array.

Can I use a set instead of a hash map?

Yes, but a hash map allows counting duplicates efficiently while tracking distinct element counts in the sliding window.

What if no subarray meets the m distinct element requirement?

Return 0, as there are no valid almost unique subarrays to sum.

Does the order of elements matter for maximum sum?

Yes, the sum depends on the actual elements in the window; order affects which subarray has the maximum sum.

How does this problem leverage array scanning plus hash lookup?

The sliding window scans the array while the hash map tracks distinct elements, enabling efficient evaluation of almost unique subarrays without full recomputation.

terminal

Solution

Solution 1: Sliding Window + Hash Table

We can traverse the array $nums$, maintain a window of size $k$, use a hash table $cnt$ to count the occurrence of each element in the window, and use a variable $s$ to sum all elements in the window. If the number of different elements in $cnt$ is greater than or equal to $m$, then we update the answer $ans = \max(ans, s)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        cnt = Counter(nums[:k])
        s = sum(nums[:k])
        ans = s if len(cnt) >= m else 0
        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

Continue Practicing

#2831 find the longest equal subarray #2875 minimum size subarray in infinite array #2799 count complete subarrays in an array