Maximum Sum of Distinct Subarrays With Length K

MediumSliding Window · Hash Map🧩 Sliding Window LeetCode #2461 ↗Updated Oct 30, 2026

Problem

Given an integer array nums and a window size k, look at every contiguous subarray of length exactly k. Among those whose elements are all different, return the largest sum. If no such window exists, return 0.

Inputnums = [1,5,4,2,9,9,9], k = 3Output15 ([4,2,9])

Inputnums = [4,4,4], k = 3Output0

Inputnums = [3,1,3,2], k = 2Output5 ([3,2])

1 ≤ k ≤ n ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵ · answer may exceed 32-bit → return long

Try it yourself

Java

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Consecutive windows differ by one element in and one element out. Keep a running sum and a frequency map: the window is all-distinct exactly when the map holds k distinct keys.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceRebuild Each Window

Time O(n · k)Space O(k)

For every start index, walk the next k elements, adding them to a fresh set and summing them. If a value repeats, the window is invalid; otherwise its sum is a candidate.

Java

public long maximumSubarraySum(int[] nums, int k) {
    long best = 0;
    for (int start = 0; start + k <= nums.length; start++) {
        Set<Integer> seen = new HashSet<>();
        long sum = 0;
        boolean distinct = true;
        for (int i = start; i < start + k; i++) {
            if (!seen.add(nums[i])) { // duplicate found
                distinct = false;
                break;
            }
            sum += nums[i];
        }
        if (distinct) best = Math.max(best, sum);
    }
    return best;
}

Straightforward, but re-scans overlapping windows — up to 10¹⁰ steps.

OptimalFixed Sliding Window + Frequency Map

Time O(n)Space O(k)

Slide a window of width k: add nums[i] to the sum and its count, and once the window is too wide remove nums[i-k] (deleting keys whose count hits 0). The map's size equals the number of distinct values, so map.size() == k means no duplicates.

Java

public long maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    long sum = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        freq.merge(nums[i], 1, Integer::sum);
        if (i >= k) { // drop the element that left the window
            int out = nums[i - k];
            sum -= out;
            if (freq.merge(out, -1, Integer::sum) == 0) freq.remove(out);
        }
        if (i >= k - 1 && freq.size() == k) {
            best = Math.max(best, sum);
        }
    }
    return best;
}

Dry runnums = [1,5,4,2,9,9,9], k = 3

s window starte window end changed

i=2
1
s
5

4
e
2

9

9

9

sum=10 distinct, best=10
i=3
1

5
s
4

2
e
9

9

9

sum=11, best=11
i=4
1

5

4
s
2

9
e
9

9

sum=15, best=15
i=5
1

5

4

2
s
9

9
e
9

size 2 < 3, skip
i=6
1

5

4

2

9
s
9

9
e
size 1, answer 15 ✔

Each element is added and removed once — linear time.

Pro tip

Since values are ≤ 10⁵, an int[] count array plus a “duplicates” counter avoids hashing overhead.

At a glance

Level	Approach	Time	Space
Brute Force	Rebuild Each Window	`O(n · k)`	`O(k)`
Optimal	Fixed Sliding Window + Frequency Map	`O(n)`	`O(k)`

Common pitfalls

Accumulating the sum in int — 10⁵ × 10⁵ overflows.
Decrementing a count without removing zero-count keys — size() becomes wrong.
Checking validity before the window has reached length k.

Interview tips

Name the trick: map size = number of distinct elements in the window.
Clarify that the answer is 0 (not -1) when no window qualifies.
Mention the array-instead-of-map optimisation given the bounded values.

Pattern

Fixed-size sliding window + counts → aggregate over every length-k window with a uniqueness or frequency condition.

My notes saved in this browser