AlgoMaster Logo

Maximum Sum of Distinct Subarrays With Length K

Last Updated: March 21, 2026

medium
3 min read

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 things matter here: the subarray must be exactly k elements long, and it must contain no duplicates. The sum part is easy once you've identified valid subarrays. The real question is how to efficiently check for duplicates as you slide through the array.

Notice that the constraint 1 <= nums[i] <= 10^5 means all values are positive. This is important because it means adding more elements always increases the sum. So among valid windows, we just want the one with the largest total.

Key Constraints:

  • nums.length up to 10^5 means we need O(n log n) or better. An O(n * k) brute force could work when k is small, but degrades to O(n^2) when k approaches n.
  • k <= nums.length so we're guaranteed at least one subarray of length k exists (though it might not be valid).
  • Values are in [1, 10^5], all positive. No negative numbers or zeros to worry about.

Approach 1: Brute Force

Intuition

The most straightforward approach: examine every subarray of length k, check if all its elements are distinct, and if so, track the maximum sum. We can use a hash set to check for duplicates within each subarray.

This is the literal translation of the problem statement into code. For each starting index, grab k elements, verify uniqueness, 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

For each new subarray, we're rebuilding the set and recomputing the sum from scratch. But adjacent subarrays overlap in k - 1 elements. What if we kept the set and sum from the previous window and just updated the one element that changed?

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. A window is valid (all distinct) when every value has a count of exactly 1, which happens when the number of distinct keys in the map equals k. So we maintain a count of distinct elements and compare it to k to check validity.

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