Maximum Sum of Almost Unique Subarray

Medium
1359.

Maximum Sum of Almost Unique Subarray

Maximum Sum of Almost Unique Subarray is a medium coding problem on arrays, hash table and sliding window, asked in Amazon and Google interviews.

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^4
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 10^5
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} m
 * @param {number} k
 * @return {number}
 */
var maxSum = function(nums, m, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 10^5

Hints for Maximum Sum of Almost Unique Subarray

  1. Hint 1

    All candidate windows have the same length k, so slide one window of length k across the array.

  2. Hint 2

    When the window moves one step, exactly one value enters and one leaves. Keep a running sum and a count per value.

  3. 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

  1. Walk i over the array, adding nums[i] to the running sum and incrementing its count (a count going 0 → 1 adds a distinct value).
  2. Once i >= k, remove nums[i - k]: subtract it from the sum and decrement its count (a count going 1 → 0 removes a distinct value).
  3. When i >= k - 1, the window nums[i-k+1 .. i] is complete: if it has at least m distinct values, update the best sum.
  4. 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 best

Java

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