Maximum Sum of Distinct Subarrays With Length K — Editorial

Opening the reading…

Intuitionwhy one moving window is enough

Every candidate has exactly k consecutive elements, so adjacent candidates differ in only two positions: one new value enters on the right and one old value leaves on the left. Recomputing each sum and rebuilding distinctness from scratch would repeat nearly all the work. Instead, keep the current window's sum and update it with those two changes.

A window is valid precisely when every value appears once. A frequency map records how many times each value occurs, while its number of keys tells you how many distinct values are present. Once the window has length k, frequency-map size k means all k positions hold different values, so its maintained sum is a candidate for the maximum.

Approach

Create an empty frequency map and set the running sum and answer to zero, because both the first window and the best valid window must be built from values that have not been processed yet.

Scan nums from left to right, adding nums[i] to the map and to the sum, because this makes the current suffix contain every value that could belong to the next length-k window.

When i is at least k, remove nums[i - k] from the map and subtract it from the sum, because that value is exactly one position outside the new window after the right endpoint advances.

Erase a value when its frequency becomes zero, because the map size is meant to count distinct values rather than positions that appeared in earlier windows.

When i is at least k - 1 and the map size equals k, compare the running sum with the answer, because only then does the current suffix have length k and contain k distinct values.

Return the answer after the scan, leaving it at zero when every length-k window contains a duplicate, which matches the required result when no valid candidate exists.

Complexitycounting updates rather than rescanning windows

MEASURE	BOUND	WHY
Time	Expected O(n); worst-case O(n^2)	Each array value is inserted once and, after it moves k positions behind the scan, removed once. Hash-map updates and lookups are expected O(1), so the total expected work is linear; adversarial collisions can make individual updates slower.
Space	O(k) extra, worst case O(n)	The map contains only values in the current window, so it has at most k entries; when k equals n, that is O(n). The returned value is a required scalar output and is not working memory.

Here n is the array length and k is the required window length. The time bound for the hash-map version is expected; a pathological hash-table collision pattern can degrade it.

Annotated solutionC++ · fixed-size sliding window with a frequency map

CPPMaintain the current window sum and erase zero-frequency values before testing whether all k values are distinct.

#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        long long sum = 0;
        long long maxSum = 0;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            ++freq[nums[i]];
            sum += nums[i];

            if (i >= k) {
                int outgoing = nums[i - k];
                if (--freq[outgoing] == 0) {
                    freq.erase(outgoing);
                }
                sum -= outgoing;
            }

            if (i >= k - 1 && static_cast<int>(freq.size()) == k) {
                maxSum = max(maxSum, sum);
            }
        }

        return maxSum;
    }
};

The order of the update is important. The incoming value is added first, then the value k positions behind the new right endpoint is removed. Only after both operations does the map describe the current length-k window. The guard i >= k - 1 prevents shorter prefixes from being considered, while the long long sum prevents a valid window's total from overflowing int.

The array-frequency alternativea predictable-constant optimization when the value bound is available

Because every nums[i] lies between 1 and 100000, you can replace the hash map with a frequency vector indexed by value. This is an optimization, not a different sliding-window idea: it removes hashing overhead and gives worst-case linear time. It uses O(100000) extra memory regardless of k, so the map version is preferable when the value range is not known or is much larger.

CPPUse the bounded value range as direct frequency-vector indices instead of hash-map keys.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        vector<int> freq(100001, 0);
        long long sum = 0;
        long long maxSum = 0;
        int distinct = 0;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            if (freq[nums[i]] == 0) {
                ++distinct;
            }
            ++freq[nums[i]];
            sum += nums[i];

            if (i >= k) {
                int outgoing = nums[i - k];
                --freq[outgoing];
                if (freq[outgoing] == 0) {
                    --distinct;
                }
                sum -= outgoing;
            }

            if (i >= k - 1 && distinct == k) {
                maxSum = max(maxSum, sum);
            }
        }

        return maxSum;
    }
};

The distinct counter replaces freq.size(). Increment it when a value's frequency changes from zero to one, and decrement it when the outgoing value's frequency changes from one to zero. The counter must describe values currently in the window, so both transitions happen alongside insertion and removal rather than when the value is first seen globally.