LeetCode Problem 2841

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

LeetCode 2841 - Maximum Sum of Almost Unique Subarray

Problem Understanding

The problem gives us an integer array nums and two integers, m and k.

We must examine every contiguous subarray whose length is exactly k. Among those subarrays, we only consider the ones that contain at least m distinct values. These are called almost unique subarrays.

For every valid subarray, we compute its sum. The goal is to return the maximum sum among all valid subarrays. If no length-k subarray contains at least m distinct elements, we return 0.

For example, if k = 4, we look at every window of exactly four consecutive elements. If a window contains at least m different numbers, it is eligible. Among all eligible windows, we choose the one with the largest sum.

The constraints are important:

• nums.length can be as large as 20,000
• nums[i] can be as large as 10^9
• k can be as large as nums.length

A brute-force solution that repeatedly scans every window and recomputes sums and distinct counts would be too slow. We need an approach that processes each element efficiently as the window moves.

A few important edge cases stand out immediately:

• No valid window exists, so the answer must be 0.
• m = 1, meaning every window is automatically valid.
• k = nums.length, meaning there is only one possible window.
• Windows may contain many duplicate values, making distinct-element counting tricky.
• Large values up to 10^9 mean sums can exceed 32-bit integer range, so Go must use int64.

Approaches

Brute Force

The most direct approach is to examine every subarray of length k.

For each starting position:

1. Build the length-k subarray.
2. Compute its sum.
3. Count how many distinct elements it contains using a hash set.
4. If the distinct count is at least m, update the answer.

This approach is correct because it explicitly evaluates every candidate window and selects the largest valid sum.

However, there are O(n) windows, and each window requires O(k) work to compute its sum and distinct count. The overall complexity becomes O(nk), which is too slow when both n and k can be around 20,000.

Optimal Sliding Window

The key observation is that all candidate subarrays have the same length k.

When moving from one window to the next:

• One element leaves the window.
• One element enters the window.

Instead of recomputing everything from scratch, we can maintain:

• The current window sum.
• A frequency map of elements inside the window.
• The number of distinct elements currently present.

As the window slides:

• Subtract the outgoing value from the sum.
• Add the incoming value to the sum.
• Update frequencies.
• Adjust the distinct count when a frequency becomes zero or changes from zero to one.

This allows each window transition to be processed in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(k)	Recomputes sum and distinct count for every window
Optimal	O(n)	O(k)	Sliding window with frequency map and running sum

Algorithm Walkthrough

Optimal Sliding Window Algorithm

1. Create a frequency hash map to store how many times each value appears inside the current window.
2. Initialize the first window of size k.

While building the first window:

• Add each value to the running sum.
• Increment its frequency.
• If a value appears for the first time, it contributes to the distinct count.

3. After the first window is built, check whether the number of distinct elements is at least m.

If it is, initialize the answer with the current window sum. 4. Start sliding the window from left to right. 5. For each slide:

• Remove the leftmost element.
• Subtract it from the running sum.
• Decrement its frequency.
• If its frequency becomes zero, remove it from the map and decrease the distinct count.

6. Add the new rightmost element.

• Add it to the running sum.
• If it was not previously present in the window, increase the distinct count.
• Increment its frequency.

7. After updating the window, check whether the distinct count is at least m.

If so, update the answer using the current window sum. 8. Continue until every length-k window has been processed. 9. Return the maximum valid sum found. If no valid window was ever encountered, return 0.

Why it works

The sliding window always represents exactly one length-k subarray. The frequency map accurately tracks how many times each value appears inside that window. Therefore, the distinct count is always correct.

Since every possible length-k subarray appears exactly once as the window slides, and we evaluate every valid window's sum, the maximum recorded sum is guaranteed to be the correct answer.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        freq = defaultdict(int)
        window_sum = 0
        distinct_count = 0

        for i in range(k):
            window_sum += nums[i]

            if freq[nums[i]] == 0:
                distinct_count += 1

            freq[nums[i]] += 1

        answer = window_sum if distinct_count >= m else 0

        for right in range(k, len(nums)):
            left_value = nums[right - k]

            window_sum -= left_value
            freq[left_value] -= 1

            if freq[left_value] == 0:
                distinct_count -= 1
                del freq[left_value]

            new_value = nums[right]

            if freq[new_value] == 0:
                distinct_count += 1

            freq[new_value] += 1
            window_sum += new_value

            if distinct_count >= m:
                answer = max(answer, window_sum)

        return answer

The implementation follows the sliding window strategy directly.

The first loop constructs the initial window and calculates both the window sum and the number of distinct elements.

After evaluating the first window, the second loop repeatedly slides the window one position to the right. Each iteration removes one element and adds one element, keeping the window size fixed at k.

The frequency map allows us to determine exactly when an element disappears from the window or appears for the first time. This keeps the distinct count accurate without rescanning the entire window.

Whenever the current window contains at least m distinct elements, we compare its sum against the best answer seen so far.

Go Solution

func maxSum(nums []int, m int, k int) int64 {
	freq := make(map[int]int)

	var windowSum int64
	distinctCount := 0

	for i := 0; i < k; i++ {
		windowSum += int64(nums[i])

		if freq[nums[i]] == 0 {
			distinctCount++
		}

		freq[nums[i]]++
	}

	var answer int64
	if distinctCount >= m {
		answer = windowSum
	}

	for right := k; right < len(nums); right++ {
		leftValue := nums[right-k]

		windowSum -= int64(leftValue)
		freq[leftValue]--

		if freq[leftValue] == 0 {
			distinctCount--
			delete(freq, leftValue)
		}

		newValue := nums[right]

		if freq[newValue] == 0 {
			distinctCount++
		}

		freq[newValue]++
		windowSum += int64(newValue)

		if distinctCount >= m && windowSum > answer {
			answer = windowSum
		}
	}

	return answer
}

The Go implementation is almost identical to the Python version.

The most important difference is the use of int64 for window sums and the final answer. Since nums[i] can be as large as 10^9 and the window can contain up to 20,000 elements, the total sum may exceed the range of a 32-bit integer.

Go maps are used for frequency tracking, and delete removes keys whose frequency drops to zero.

Worked Examples

Example 1

Input

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

Initial window:

[2,6,7,3]

Window	Sum	Distinct Count	Valid?	Best
[2,6,7,3]	18	4	Yes	18

Slide once:

Removed	Added
2	1

Window becomes:

[6,7,3,1]

Window	Sum	Distinct Count	Valid?	Best
[6,7,3,1]	17	4	Yes	18

Slide again:

Removed	Added
6	7

Window becomes:

[7,3,1,7]

Window	Sum	Distinct Count	Valid?	Best
[7,3,1,7]	18	3	Yes	18

Final answer:

18

Example 2

Input

nums = [5,9,9,2,4,5,4]
m = 1
k = 3

Since m = 1, every window is valid.

Window	Sum
[5,9,9]	23
[9,9,2]	20
[9,2,4]	15
[2,4,5]	11
[4,5,4]	13

Maximum sum:

23

Example 3

Input

nums = [1,2,1,2,1,2,1]
m = 3
k = 3

Window	Distinct Count
[1,2,1]	2
[2,1,2]	2
[1,2,1]	2
[2,1,2]	2
[1,2,1]	2

Every window has only two distinct values.

No valid window exists, therefore:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the window at most once
Space	O(k)	Frequency map stores at most the elements inside one window

The algorithm performs a constant amount of work whenever the window moves. Since there are n elements and each is added and removed at most once, the total runtime is linear. The frequency map can never contain more than k distinct values because the window size is fixed at k.

Test Cases

from typing import List

s = Solution()

assert s.maxSum([2,6,7,3,1,7], 3, 4) == 18  # example 1
assert s.maxSum([5,9,9,2,4,5,4], 1, 3) == 23  # example 2
assert s.maxSum([1,2,1,2,1,2,1], 3, 3) == 0  # example 3

assert s.maxSum([5], 1, 1) == 5  # single element array
assert s.maxSum([5], 1, 1) == 5  # minimum constraints

assert s.maxSum([1,2,3,4], 4, 4) == 10  # entire array is the only window
assert s.maxSum([1,1,1,1], 2, 2) == 0  # no valid window

assert s.maxSum([1,2,2,3], 3, 4) == 8  # exactly m distinct values
assert s.maxSum([10,10,10,10], 1, 2) == 20  # all duplicates but valid

assert s.maxSum([1,2,3,4,5], 2, 2) == 9  # best window at end
assert s.maxSum([5,4,3,2,1], 2, 2) == 9  # best window at beginning

assert s.maxSum([1000000000,1000000000], 1, 2) == 2000000000  # large values

assert s.maxSum([1,2,1,3,4], 3, 3) == 8  # valid window appears later
assert s.maxSum([4,4,4,5,6], 2, 3) == 15  # duplicates transitioning to distinct

Test Summary

Test	Why
[2,6,7,3,1,7], m=3, k=4	Official example
[5,9,9,2,4,5,4], m=1, k=3	Every window valid
[1,2,1,2,1,2,1], m=3, k=3	No valid window
[5], m=1, k=1	Smallest possible input
[1,2,3,4], m=4, k=4	Single window case
[1,1,1,1], m=2, k=2	Impossible distinct requirement
[1,2,2,3], m=3, k=4	Distinct count exactly equals m
[10,10,10,10], m=1, k=2	All duplicates
[1,2,3,4,5], m=2, k=2	Maximum window near end
[5,4,3,2,1], m=2, k=2	Maximum window near start
Large values near 10^9	Overflow safety
[1,2,1,3,4], m=3, k=3	Valid window appears later
[4,4,4,5,6], m=2, k=3	Frequency updates when duplicates leave

Edge Cases

No Valid Window Exists

A common mistake is assuming at least one window satisfies the distinct-element requirement. Consider:

nums = [1,1,1,1]
m = 2
k = 2

Every window contains only one distinct value. The implementation initializes the answer to 0 and only updates it when a valid window is encountered. Therefore it correctly returns 0.

Entire Array Is One Window

When k = nums.length, only a single candidate window exists.

nums = [1,2,3,4]
m = 4
k = 4

The algorithm builds the first window, evaluates it, and never enters the sliding phase. This naturally handles the case without any special logic.

Large Numbers

Each value can be as large as 10^9, and there may be up to 20,000 values in a window.

A window sum can therefore reach approximately:

20,000 × 10^9 = 2 × 10^13

This exceeds 32-bit integer limits. The Go solution uses int64 for all sums and the final answer, preventing overflow. Python integers automatically support arbitrarily large values, so no special handling is required there.

Distinct Count Changes Due to Duplicates

When removing an element from the window, the distinct count should only decrease if that element completely disappears from the window.

For example:

Window: [7,7,3,1]

Removing one 7 should not reduce the distinct count because another 7 still remains. The frequency map correctly distinguishes between reducing a frequency and removing a value entirely, ensuring accurate distinct-element tracking throughout the sliding process.