#2461

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Sum of Distinct Subarrays With Length K

Find the maximum sum of all distinct-element subarrays of length k using array scanning and hash lookup techniques.

Problem Statement

Given an integer array nums and an integer k, identify all contiguous subarrays of length k where every element is unique. Compute the sum of each valid subarray.

Return the maximum sum among these subarrays. If no subarray meets the distinct element requirement, return 0. Constraints: 1 <= k <= nums.length <= 105 and 1 <= nums[i] <= 105.

Examples

Example 1

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

Output: 15

The subarrays of nums with length 3 are:

[1,5,4] which meets the requirements and has a sum of 10.
[5,4,2] which meets the requirements and has a sum of 11.
[4,2,9] which meets the requirements and has a sum of 15.
[2,9,9] which does not meet the requirements because the element 9 is repeated.
[9,9,9] which does not meet the requirements because the element 9 is repeated. We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2

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

Output: 0

The subarrays of nums with length 3 are:

[4,4,4] which does not meet the requirements because the element 4 is repeated. We return 0 because no subarrays meet the conditions.

Constraints

1 <= k <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Sliding Window With Hash Set

Initialize a hash set to track elements in the current window. Add elements as the window grows and remove the element exiting the window. Skip any window with duplicates.

Maintain Running Sum

Keep a running sum of elements in the window. Add the new element and subtract the leaving element to avoid recomputing the sum each time, ensuring O(1) updates per move.

Track Maximum Sum

Each time a valid window with k distinct elements is found, compare its sum with the current maximum and update if larger. After scanning the array, return the maximum sum or 0 if none found.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because each element enters and leaves the window at most once. Space complexity is O(N) due to the hash set tracking distinct elements.

What Interviewers Usually Probe

Can you explain which elements change when the window moves by one position?
How do you efficiently check for duplicates in each subarray?
What data structure ensures constant-time add and remove for sliding windows?

Common Pitfalls or Variants

Common pitfalls

Forgetting to remove the outgoing element from the hash set when sliding the window.
Recomputing the sum from scratch instead of maintaining a running sum.
Including subarrays with repeated elements when only distinct sums are allowed.

Follow-up variants

Find maximum sum of subarrays of length k allowing at most one duplicate.
Compute maximum sum for subarrays of any length with distinct elements.
Return the subarray itself rather than just the maximum sum.

FAQ

What is the key strategy for Maximum Sum of Distinct Subarrays With Length K?

Use a sliding window of size k and a hash set to ensure elements are distinct while tracking the sum efficiently.

How do I handle duplicates in the subarray efficiently?

Remove the element leaving the window from the hash set and skip any window where a duplicate exists in the set.

What if no subarray of length k has distinct elements?

Return 0 because no valid subarray meets the distinct-element requirement.

Why is the sliding window approach preferred here?

It allows O(1) updates for sum and hash set operations per window shift, giving O(N) overall time.

Can this method be adapted for different subarray lengths?

Yes, by changing k and maintaining the same sliding window with hash set logic to track distinct elements.

terminal

Solution

Solution 1: Sliding Window + Hash Table

We maintain a sliding window of length $k$, use a hash table $cnt$ to record the count of each number in the window, and use a variable $s$ to record the sum of all numbers in the window. Each time we slide the window, if all numbers in the window are unique, we update the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#2537 count the number of good subarrays #2653 sliding subarray beauty #2260 minimum consecutive cards to pick up