AlgoMaster Logo

Maximum Sum of Distinct Subarrays With Length K

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We need to find the maximum sum among all subarrays of exactly length k where every element in the subarray is unique. If no such subarray exists, return 0.

Two conditions define a valid subarray: it must be exactly k elements long, and it must contain no duplicates. Computing the sum is trivial once a subarray is known to be valid. The harder part is checking for duplicates efficiently as we move across the array.

The constraint 1 <= nums[i] <= 10^5 means all values are positive. Among valid windows, we want the one with the largest total, and there is no benefit to anything other than tracking that maximum directly.

Key Constraints:

  • nums.length up to 10^5 means an O(n) or O(n log n) solution is needed. An O(n * k) brute force is fine when k is small, but degrades to O(n^2) when k approaches n, which is too slow at this size.
  • The window sum can reach k elements each as large as 10^5, and k itself can be up to 10^5, so the sum can approach 10^5 * 10^5 = 10^10. That exceeds the 32-bit signed integer range (about 2.1 * 10^9), so the sum and the return value must use a 64-bit type. This is why every implementation returns long / int64 / i64.
  • k <= nums.length so at least one subarray of length k exists, though it may not be valid.
  • Values are in [1, 10^5], all positive. There are no negatives or zeros.

Approach 1: Brute Force

Intuition

Examine every subarray of length k, check whether all its elements are distinct, and track the maximum sum among the valid ones. A hash set detects duplicates within each subarray: insert elements one by one, and if an insert finds a value already present, the subarray has a duplicate.

This translates the problem statement directly into code. For each starting index, take the next k elements, verify uniqueness, and compute the sum.

Algorithm

  1. Initialize maxSum = 0
  2. For each starting index i from 0 to n - k:
    • Create an empty set and a running sum for this subarray
    • Add elements nums[i] through nums[i + k - 1] to the set while accumulating the sum
    • If a duplicate is found (element already in set), skip this subarray
    • If the set has k elements (all distinct) and the sum exceeds maxSum, update maxSum
  3. Return maxSum

Example Walkthrough

1i=0: Check subarray [1,5,4]
0
1
i
1
5
2
4
3
2
4
9
5
9
6
9
1/9

Code

This rebuilds the set and recomputes the sum from scratch for every subarray, even though adjacent subarrays share k - 1 elements. The next approach reuses that overlap: carry the set and the sum from one window to the next, updating only for the single element that leaves and the single element that enters.

Approach 2: Sliding Window with Hash Map

Intuition

When we slide the window one position to the right, exactly one element leaves (the leftmost) and one element enters (the new rightmost). Instead of rebuilding everything, we can maintain a running sum and a frequency map, updating both incrementally.

The frequency map tracks how many times each value appears in the current window. We use the map's size as the validity test, and that test is exact for one reason: the window always holds exactly k elements, so its k values are spread across the map's keys. If those values land on k distinct keys, each key was hit once and every element is distinct. If any value repeats, two of the k elements share a key, the map has fewer than k keys, and the window is invalid. Removing zero-count entries immediately keeps the map size equal to the true number of distinct values. Maintaining the sum incrementally, by adding the entering value and subtracting the leaving value, keeps it correct without rescanning the window.

Algorithm

  1. Create a frequency map and initialize windowSum = 0, maxSum = 0
  2. Build the first window: add elements nums[0] through nums[k-1] to the map and sum
  3. If the first window has k distinct elements (map size equals k), update maxSum
  4. Slide the window from index k to n - 1:
    • Add nums[i] to the map and add its value to windowSum
    • Remove nums[i - k] from the map and subtract its value from windowSum
    • If an element's count drops to 0, remove it from the map entirely
    • If the map size equals k (all distinct), update maxSum
  5. Return maxSum

Example Walkthrough

1Build initial window [1,5,4]: sum=10, map={1:1,5:1,4:1}
0
1
1
5
2
4
3
2
4
9
5
9
6
9
1/11

Code