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.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^51 <= nums[i] <= 10^4
Hints for Maximum Sum of Distinct Subarrays With Length K
Hint 1
Every candidate is a window of fixed length
k— slide it one step at a time.Hint 2
Maintain the window's sum and a count of each value inside it as elements enter and leave.
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
- Keep
sum, a frequency mapcnt, anddistinct= the number of values with a non-zero count. - For each index
i, addnums[i](bumpdistinctwhen its count goes 0 → 1). - If
i >= k, removenums[i - k](dropdistinctwhen its count goes 1 → 0). - Once the window has
kelements, ifdistinct == kupdate 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
distinctonly 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 bestJava
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