Maximum Sum of Distinct Subarrays With Length K

Medium
1165.

Maximum Sum of Distinct Subarrays With Length K

Maximum Sum of Distinct Subarrays With Length K is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Google and Microsoft interviews.

Among all subarrays of nums that have length exactly k and consist of k distinct values, return the largest sum. If no subarray of length k has all-distinct values, return 0.

Note: the original problem allows values up to 10^5 and returns a 64-bit sum; here nums[i] <= 10^4, so the answer always fits in a 32-bit integer.

Example 1

Input
nums = [3,6,6,2,7,4,4], k = 3
Output
15
Explanation
The windows with distinct values are `[6,2,7]` (sum 15) and `[2,7,4]` (sum 13); the rest repeat a value.

Example 2

Input
nums = [5,5,5], k = 2
Output
0

Example 3

Input
nums = [1,2,3], k = 3
Output
6

Constraints

  • 1 <= k <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumSubarraySum = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Sum of Distinct Subarrays With Length K — Solution

Maximum Sum of Distinct Subarrays With Length K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Sum of Distinct Subarrays With Length K is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Google and Microsoft interviews.

Problem statement

Among all subarrays of nums that have length exactly k and consist of k distinct values, return the largest sum. If no subarray of length k has all-distinct values, return 0.

Note: the original problem allows values up to 10^5 and returns a 64-bit sum; here nums[i] <= 10^4, so the answer always fits in a 32-bit integer.

Example 1

Input: nums = [3,6,6,2,7,4,4], k = 3
Output: 15
Explanation: The windows with distinct values are `[6,2,7]` (sum 15) and `[2,7,4]` (sum 13); the rest repeat a value.

Example 2

Input: nums = [5,5,5], k = 2
Output: 0

Example 3

Input: nums = [1,2,3], k = 3
Output: 6

Constraints

  • 1 <= k <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Hints for Maximum Sum of Distinct Subarrays With Length K

  1. Hint 1

    Every candidate is a window of fixed length k — slide it one step at a time.

  2. Hint 2

    Maintain the window's sum and a count of each value inside it as elements enter and leave.

  3. Hint 3

    The window is all-distinct exactly when the number of different values in it equals k.

How to solve Maximum Sum of Distinct Subarrays With Length K

A fixed-size sliding window with a frequency map: each step adds one element and removes one, updating the sum and the number of distinct values in O(1).

Approach

  1. Keep sum, a frequency map cnt, and distinct = the number of values with a non-zero count.
  2. For each index i, add nums[i] (bump distinct when its count goes 0 → 1).
  3. If i >= k, remove nums[i - k] (drop distinct when its count goes 1 → 0).
  4. Once the window has k elements, if distinct == k update the best sum. Return the best (0 if never updated).

Why it works

A window of k elements has k distinct values exactly when no value repeats, so distinct == k is the precise test. The window visits every length-k subarray once, so the maximum over the valid ones is found.

Complexity

  • Time — O(n)
  • Space — O(k)

Pitfalls

  • Return 0, not a negative sentinel, when no window qualifies.
  • Update distinct only on 0 ↔ 1 transitions of a count.
  • With the original limits the sum needs 64 bits.

Reference solution

Python

from typing import List

def maximumSubarraySum(nums: List[int], k: int) -> int:
    cnt = {}
    distinct = 0
    total = 0
    best = 0
    for i, x in enumerate(nums):
        total += x
        cnt[x] = cnt.get(x, 0) + 1
        if cnt[x] == 1:
            distinct += 1
        if i >= k:
            y = nums[i - k]
            total -= y
            cnt[y] -= 1
            if cnt[y] == 0:
                distinct -= 1
        if i >= k - 1 and distinct == k:
            best = max(best, total)
    return best

Java

public static int maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int distinct = 0;
    long total = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        total += x;
        if (cnt.merge(x, 1, Integer::sum) == 1) distinct++;
        if (i >= k) {
            int y = nums[i - k];
            total -= y;
            int cy = cnt.get(y) - 1;
            cnt.put(y, cy);
            if (cy == 0) distinct--;
        }
        if (i >= k - 1 && distinct == k && total > best) best = total;
    }
    return (int) best;
}

C++

int maximumSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    int distinct = 0;
    long long total = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        int x = nums[i];
        total += x;
        if (++cnt[x] == 1) distinct++;
        if (i >= k) {
            int y = nums[i - k];
            total -= y;
            if (--cnt[y] == 0) distinct--;
        }
        if (i >= k - 1 && distinct == k && total > best) best = total;
    }
    return (int)best;
}

JavaScript

var maximumSubarraySum = function(nums, k) {
    var cnt = new Map();
    var distinct = 0, total = 0, best = 0;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        total += x;
        var cx = (cnt.get(x) || 0) + 1;
        cnt.set(x, cx);
        if (cx === 1) distinct++;
        if (i >= k) {
            var y = nums[i - k];
            total -= y;
            var cy = cnt.get(y) - 1;
            cnt.set(y, cy);
            if (cy === 0) distinct--;
        }
        if (i >= k - 1 && distinct === k && total > best) best = total;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets