Maximum Sum of Distinct Subarrays With Length K

35 min · maxSumDistinctK()

A playlist curator wants a run of k tracks with no repeated artist. A high total score doesn't count if even one artist appears twice.

Given a positive-integer array nums and an integer k, inspect every contiguous subarray — a group of neighboring values with no gaps — of exactly k elements. A window is distinct when every value inside it appears once. Return the largest sum among the distinct windows, or 0 when none qualifies.

A few ground rules:

The window must contain exactly k neighboring values.
A repeated value disqualifies that entire window, even if its sum would otherwise be the largest.
All values are positive, so 0 can unambiguously mean that no valid window exists.
The answer can exceed a signed 32-bit integer; keep sums in the signature's 64-bit long result type.

Constraints

1 <= k <= nums.length <= 100_000
1 <= nums[i] <= 100_000

Hints

Start window by window

For each starting position, use a set to detect a repeated value while adding the next k numbers. This gives you a correct baseline and exposes the repeated work.

Keep two facts about the window

As the range moves, you need its sum and enough information to know whether all k values are different. A map from value to count maintains both moves safely.

Remove before you judge

Add the incoming value, then remove the value that fell off the left once the range grows beyond k. A length-k window is valid exactly when the map has k keys.

Follow-up

Could you process the same input as a stream while storing only the current window and its counts?

Visible cases

Examples

Example 1

ready

Input: nums = [ 1, 5, 4, 2, 9, 9, 9 ] k = 3
Expected: 15
Why: [4, 2, 9] is distinct and sums to 15

Example 2

ready

Input: nums = [ 4, 4, 4 ] k = 2
Expected: 0
Why: every length-2 window repeats 4, so none qualifies

Example 3

ready

Input: nums = [ 9, 9, 8, 1, 2 ] k = 3
Expected: 18
Why: the largest raw sum repeats 9; [9, 8, 1] is the best valid window

Example 4

ready

Input: nums = [ 5, 1, 3, 5, 2, 3, 4, 1 ] k = 3
Expected: 10
Why: two distinct windows tie at the maximum sum of 10

Interview signal

Asked at

AmazonGoogleTikTok

Check every window

Build a fresh set for each length-k window. While scanning that window, add its values and stop as soon as one repeats. Only a window with k set entries may update the answer.

def max_sum_distinct_k(nums: list[int], k: int) -> int:
    best = 0
 
    for start in range(len(nums) - k + 1):
        seen: set[int] = set()
        window_sum = 0
 
        for i in range(start, start + k):
            if nums[i] in seen:
                break
            seen.add(nums[i])
            window_sum += nums[i]
 
        if len(seen) == k:
            best = max(best, window_sum)
 
    return best

Time O(n · k) in the worst case, when every window is distinct and all k values must be checked. Space O(k) for the set.

Sliding window with counts

A frequency map stores how many times each value occurs in the current window. Move the right edge one step at a time, adding the incoming value to the sum and map. Once the range grows beyond k, subtract the outgoing value and reduce its count, deleting the key when its count reaches zero.

def max_sum_distinct_k(nums: list[int], k: int) -> int:
    counts: dict[int, int] = {}
    window_sum = 0
    best = 0
 
    for right, value in enumerate(nums):
        window_sum += value
        counts[value] = counts.get(value, 0) + 1
 
        if right >= k:
            outgoing = nums[right - k]
            window_sum -= outgoing
            counts[outgoing] -= 1
            if counts[outgoing] == 0:
                del counts[outgoing]
 
        if right >= k - 1 and len(counts) == k:
            best = max(best, window_sum)
 
    return best

After the removal step, the range contains exactly k values whenever right >= k - 1. It has k map keys only when each value occurs once, so that one size check is a complete distinctness test.

Time O(n) — each value enters and leaves once, with expected O(1) map work. Space O(k) — the map holds at most the current window's values.

The maximum valid sum can reach 10_000_000_000; use a 64-bit running sum in languages with fixed-width integers.

Loading editor

Console

ready to run

Ready to run.

4 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraynums: int[] · k: int

Expected

Run: visible + custom · Submit: full suite