Maximum Sum of Almost Unique Subarray — Problem & Solution
Maximum Sum of Almost Unique Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Sum of Almost Unique Subarray is a medium coding problem on arrays, hash table and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Google
- 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
You are given an integer array nums and two positive integers m and k.
A contiguous subarray of length exactly k is almost unique when it contains at least m distinct values.
Return the maximum sum over all almost unique subarrays of length k. If there is none, return 0.
CodeKairo note: the original allows nums[i] up to 10^9 and returns a 64-bit sum; here nums[i] <= 10^5, so every window sum fits in a 32-bit integer.
Example 1
Input: nums = [3,8,2,8,1,4], m = 3, k = 4
Output: 21
Explanation: The windows are `[3,8,2,8]` (3 distinct, sum 21), `[8,2,8,1]` (3 distinct, sum 19) and `[2,8,1,4]` (4 distinct, sum 15).
Example 2
Input: nums = [6,6,1,6,6], m = 2, k = 2
Output: 7
Explanation: Only `[6,1]` and `[1,6]` have two distinct values.
Example 3
Input: nums = [4,4,4,4], m = 2, k = 3
Output: 0
Explanation: No window has two distinct values.
Constraints
1 <= nums.length <= 2 * 10^41 <= m <= k <= nums.length1 <= nums[i] <= 10^5
Hints for Maximum Sum of Almost Unique Subarray
Hint 1
All candidate windows have the same length
k, so slide one window of lengthkacross the array.Hint 2
When the window moves one step, exactly one value enters and one leaves. Keep a running sum and a count per value.
Hint 3
The number of distinct values is the number of keys with a positive count — update it when a count goes 0 → 1 or 1 → 0.
How to solve Maximum Sum of Almost Unique Subarray
A fixed-length sliding window with a frequency map gives each window's sum and distinct count in O(1) amortised per step.
Approach
- Walk
iover the array, addingnums[i]to the running sum and incrementing its count (a count going 0 → 1 adds a distinct value). - Once
i >= k, removenums[i - k]: subtract it from the sum and decrement its count (a count going 1 → 0 removes a distinct value). - When
i >= k - 1, the windownums[i-k+1 .. i]is complete: if it has at leastmdistinct values, update the best sum. - Return the best sum (0 if no window qualified).
Why it works
Every length-k window is visited exactly once, and the map always reflects exactly the elements inside the current window, so its number of positive entries is the window's distinct count. Because all values are positive the empty answer 0 is below every real window sum, which is why 0 can stand for "none".
Complexity
- Time —
O(n) - Space —
O(k)
Pitfalls
- Recomputing the distinct count of each window from scratch is O(n · k).
- Delete (or ignore) keys whose count drops to 0, or the map's size overstates the distinct count.
- With the original 10^9 bound the sum needs 64 bits; keep the running sum in a 64-bit variable anyway.
Reference solution
Python
from typing import List
def maxSum(nums: List[int], m: int, k: int) -> int:
count = {}
total = 0
best = 0
for i, v in enumerate(nums):
total += v
count[v] = count.get(v, 0) + 1
if i >= k:
old = nums[i - k]
total -= old
count[old] -= 1
if count[old] == 0:
del count[old]
if i >= k - 1 and len(count) >= m and total > best:
best = total
return bestJava
public static int maxSum(int[] nums, int m, int k) {
Map<Integer, Integer> count = new HashMap<>();
long sum = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
count.merge(nums[i], 1, Integer::sum);
if (i >= k) {
int old = nums[i - k];
sum -= old;
int c = count.get(old) - 1;
if (c == 0) count.remove(old); else count.put(old, c);
}
if (i >= k - 1 && count.size() >= m && sum > best) best = sum;
}
return (int) best;
}C++
int maxSum(vector<int>& nums, int m, int k) {
unordered_map<int, int> count;
long long sum = 0, best = 0;
for (int i = 0; i < (int) nums.size(); i++) {
sum += nums[i];
count[nums[i]]++;
if (i >= k) {
int old = nums[i - k];
sum -= old;
if (--count[old] == 0) count.erase(old);
}
if (i >= k - 1 && (int) count.size() >= m && sum > best) best = sum;
}
return (int) best;
}JavaScript
var maxSum = function(nums, m, k) {
var count = new Map();
var sum = 0, best = 0;
for (var i = 0; i < nums.length; i++) {
sum += nums[i];
count.set(nums[i], (count.get(nums[i]) || 0) + 1);
if (i >= k) {
var old = nums[i - k];
sum -= old;
var c = count.get(old) - 1;
if (c === 0) count.delete(old); else count.set(old, c);
}
if (i >= k - 1 && count.size >= m && sum > best) best = sum;
}
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