LeetCode Problem 2461

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

Solution

That prompt contains two different LeetCode problems merged together, but the second problem, LeetCode 2461 - Maximum Sum of Distinct Subarrays With Length K, appears to be the target because the detailed sections and code stubs at the end correspond to it.

I will provide the full solution guide for LeetCode 2461.

LeetCode 2461 - Maximum Sum of Distinct Subarrays With Length K

Problem Understanding

The problem asks us to examine all contiguous subarrays of length k and determine which of them satisfy an important constraint: every element inside the subarray must be distinct. Among all valid subarrays, we must return the largest possible sum. If no valid subarray exists, the answer is 0.

In other words, we are sliding a fixed-size window of length k across the array and checking two conditions at every position. First, the subarray must contain exactly k distinct numbers, meaning no duplicates are allowed. Second, we compute the sum of the numbers inside that window. Our goal is to find the maximum such sum.

The input consists of an integer array nums and an integer k. The array contains positive integers, and k specifies the exact size of subarrays we are allowed to consider. The output is a single integer representing the maximum valid subarray sum.

The constraints are important:

• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Since the array can contain up to 100,000 elements, any solution worse than roughly O(n log n) will likely be too slow. A brute-force approach that repeatedly scans subarrays would be inefficient. This strongly suggests that we need a linear-time strategy.

Several edge cases stand out immediately. If every window contains duplicates, the answer should remain 0. If k = 1, every single element forms a valid distinct subarray, so the answer becomes the maximum element. If k equals the entire array length, we only have one candidate window, which must either contain all unique values or return 0.

Approaches

Brute Force Approach

A straightforward approach is to generate every subarray of length k, check whether all elements are distinct, and compute its sum.

For each starting position, we could:

1. Extract the subarray of size k.
2. Use a set to verify uniqueness.
3. Compute the sum of the subarray.
4. Update the maximum if the subarray is valid.

This method is correct because it explicitly checks every possible candidate window and guarantees that no valid answer is missed.

However, it is inefficient. There are O(n) windows, and each one requires O(k) work to build a set and compute the sum. In the worst case, this becomes O(n * k), which is too slow when both n and k can be as large as 100,000.

Optimal Approach

The key insight is that adjacent subarrays of length k overlap heavily. When moving from one window to the next, we only remove one element and add one new element. Recomputing everything from scratch wastes work.

This observation naturally leads to a sliding window technique.

We maintain:

• A running sum of the current window.
• A hash map that stores the frequency of elements inside the window.

The hash map allows us to determine whether all elements are distinct. If the number of unique keys equals k, then every element in the window appears exactly once.

As the window slides:

• Remove the leftmost element.
• Add the new rightmost element.
• Update frequencies efficiently.
• Adjust the running sum in constant time.

This reduces the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(k)	Recomputes sum and uniqueness for every window
Optimal	O(n)	O(k)	Sliding window with frequency map

Algorithm Walkthrough

1. Initialize a hash map to track element frequencies inside the current window. Also initialize variables for the current window sum and the maximum valid sum.
2. Build the first window of size k. For each element:

• Add it to the running sum.
• Increase its frequency in the hash map.

3. After constructing the first window, check whether the window contains k distinct elements. We know this is true when the number of keys in the frequency map equals k. If valid, update the maximum sum.
4. Start sliding the window from left to right. For every new position:

• Remove the outgoing element from the left side.
• Decrease its frequency.
• If its frequency becomes zero, remove it from the map entirely.
• Add the incoming element on the right side.
• Increase its frequency.
• Update the running sum by subtracting the outgoing value and adding the incoming value.

5. After each slide, check whether the window has exactly k distinct elements. If so, compare the current sum against the maximum and update if necessary.
6. Continue until all windows have been processed.

Why it works

The sliding window always represents exactly one contiguous subarray of length k. The running sum ensures we can compute subarray sums in constant time, while the frequency map accurately tracks duplicates. A window is valid precisely when the number of unique elements equals k, guaranteeing every element is distinct. Since every possible window is examined exactly once, the algorithm cannot miss the optimal answer.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        frequency = defaultdict(int)
        current_sum = 0
        max_sum = 0

        # Build the first window
        for i in range(k):
            current_sum += nums[i]
            frequency[nums[i]] += 1

        # Check the first window
        if len(frequency) == k:
            max_sum = current_sum

        # Slide the window
        for right in range(k, len(nums)):
            left = right - k

            outgoing = nums[left]
            incoming = nums[right]

            current_sum -= outgoing
            frequency[outgoing] -= 1

            if frequency[outgoing] == 0:
                del frequency[outgoing]

            current_sum += incoming
            frequency[incoming] += 1

            if len(frequency) == k:
                max_sum = max(max_sum, current_sum)

        return max_sum

The implementation begins by creating a frequency map using defaultdict(int) so missing keys automatically start at zero. We also initialize two variables: current_sum for the active window and max_sum for the best answer found so far.

The first loop constructs the initial window of size k. Instead of recalculating sums later, we maintain a running total as elements enter and leave the window.

Once the initial window is ready, we check whether its number of unique elements equals k. If true, the window contains no duplicates and becomes a candidate answer.

The second loop handles window movement. Each iteration removes one element from the left and adds one on the right. Frequencies are updated accordingly, and elements whose count reaches zero are removed from the map. This removal step matters because len(frequency) must accurately reflect the number of distinct elements.

Finally, every valid window updates max_sum, and the answer is returned.

Go Solution

func maximumSubarraySum(nums []int, k int) int64 {
	frequency := make(map[int]int)
	var currentSum int64
	var maxSum int64

	// Build the first window
	for i := 0; i < k; i++ {
		currentSum += int64(nums[i])
		frequency[nums[i]]++
	}

	// Check the first window
	if len(frequency) == k {
		maxSum = currentSum
	}

	// Slide the window
	for right := k; right < len(nums); right++ {
		left := right - k

		outgoing := nums[left]
		incoming := nums[right]

		currentSum -= int64(outgoing)
		frequency[outgoing]--

		if frequency[outgoing] == 0 {
			delete(frequency, outgoing)
		}

		currentSum += int64(incoming)
		frequency[incoming]++

		if len(frequency) == k && currentSum > maxSum {
			maxSum = currentSum
		}
	}

	return maxSum
}

The Go implementation follows the same logic but uses a map[int]int for frequency counting. Since subarray sums can become large, we use int64 for both currentSum and maxSum. This prevents overflow and matches the required function signature. Unlike Python, Go requires explicit deletion of keys using delete() when a frequency reaches zero.

Worked Examples

Example 1

Input:

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

We slide a window of size 3.

Window	Frequency Map	Distinct?	Sum	Max Sum
[1,5,4]	{1:1, 5:1, 4:1}	Yes	10	10
[5,4,2]	{5:1, 4:1, 2:1}	Yes	11	11
[4,2,9]	{4:1, 2:1, 9:1}	Yes	15	15
[2,9,9]	{2:1, 9:2}	No	20	15
[9,9,9]	{9:3}	No	27	15

The largest valid distinct-window sum is 15.

Example 2

Input:

nums = [4,4,4]
k = 3

Window	Frequency Map	Distinct?	Sum	Max Sum
[4,4,4]	{4:3}	No	12	0

Since no valid window exists, the answer remains 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the sliding window once
Space	O(k)	The frequency map stores at most k distinct values

The algorithm is linear because every array element is processed a constant number of times. The hash map never grows beyond the size of the window, so memory usage is bounded by O(k).

Test Cases

sol = Solution()

assert sol.maximumSubarraySum([1, 5, 4, 2, 9, 9, 9], 3) == 15  # Example 1
assert sol.maximumSubarraySum([4, 4, 4], 3) == 0  # Example 2

assert sol.maximumSubarraySum([5], 1) == 5  # Single element array
assert sol.maximumSubarraySum([1, 2, 3, 4], 1) == 4  # k = 1
assert sol.maximumSubarraySum([1, 2, 3, 4], 4) == 10  # Entire array valid
assert sol.maximumSubarraySum([1, 2, 2, 3], 4) == 0  # Entire array invalid

assert sol.maximumSubarraySum([1, 2, 3, 2, 5], 3) == 10  # Multiple valid windows
assert sol.maximumSubarraySum([9, 9, 9, 9], 2) == 0  # No distinct window
assert sol.maximumSubarraySum([1, 1, 2, 3], 2) == 5  # Window becomes valid later
assert sol.maximumSubarraySum([100000, 99999, 99998], 2) == 199999  # Large values

Test	Why
[1,5,4,2,9,9,9], k=3	Validates the main example
[4,4,4], k=3	Ensures no valid subarray returns 0
[5], k=1	Smallest possible input
[1,2,3,4], k=1	Every element becomes a valid window
[1,2,3,4], k=4	Entire array is one valid window
[1,2,2,3], k=4	Entire array invalid due to duplicates
[1,2,3,2,5], k=3	Tests mixed valid and invalid windows
[9,9,9,9], k=2	Repeated duplicates throughout
[1,1,2,3], k=2	Valid window appears after invalid ones
[100000,99999,99998], k=2	Large values ensure sum handling works

Edge Cases

One important edge case occurs when k = 1. In this situation, every single-element subarray automatically contains distinct values because there is only one element. A buggy implementation might still perform unnecessary duplicate checks, but this algorithm naturally handles it because every frequency map contains exactly one key.

Another important case happens when all values are repeated, such as [4,4,4,4]. Since every window contains duplicates, no valid subarray exists. The implementation correctly returns 0 because max_sum is initialized to zero and only updated for valid windows.

A third edge case appears when k equals the array length. There is only one possible subarray to evaluate. If all elements are unique, we return the total sum. Otherwise, we return 0. The implementation handles this seamlessly because the first window construction already covers the entire array and no sliding occurs afterward.