Abstract / Summary

Find the highest sum of a subarray where at most one number repeats.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 41% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sliding Window

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method maxSum that scans an integer list nums with a fixed-size sliding window of length k. While the window moves from left to right, it keeps track of the distinct values inside the window using a frequency map (have). Whenever the window contains at least m different numbers, the current window sum (total) is a candidate for the answer, and the maximum of all such sums is stored in result. The algorithm returns this maximum sum after the entire list has been processed.

Sliding Window Initialization

At the start of the method, three variables are prepared:

result = 0
have   = defaultdict(int)
total  = 0

result holds the best sum found so far. have is a dictionary that maps each integer in the current window to its occurrence count. total accumulates the sum of the elements currently inside the window. These initial values represent an empty window positioned before the first element of nums.

Maintaining the Frequency Map

The core of the sliding-window logic is inside the for loop that iterates over nums with the index right and the element n. When the window exceeds the prescribed length k, the leftmost element is removed:

if right >= k:
    left = right - k
    x = nums[left]
    have[x] -= 1
    if have[x] == 0:
        del have[x]
    total -= x

The code computes the index of the element that falls out of the window (left). It decrements the count for that element in have. If the count drops to zero, the key is deleted, which keeps the size of have equal to the number of distinct values present in the window. The element’s value is also subtracted from total, maintaining an accurate running sum.

Adding the New Element

After any necessary removal, the algorithm incorporates the new element at the right edge of the window:

have[n] += 1
total   += n

The frequency map is updated to reflect the additional occurrence, and the element’s value contributes to the window sum.

Checking the Distinct-Count Condition

Once the window has been updated, the method evaluates whether the window satisfies the requirement of containing at least m distinct numbers:

if len(have) >= m:
    result = max(result, total)

len(have) directly yields the count of unique values because the map only retains entries with positive frequencies. When the condition holds, result is updated with the larger of its current value and the present window sum.

Edge Cases Handled

The algorithm gracefully handles several boundary situations without explicit special-case code. When k is larger than the length of nums, the removal block never executes because right never reaches k. Consequently, the window simply grows until the end of the list, and the distinct-count check still applies to the partially filled window. If m exceeds the possible number of distinct elements in any window, the condition len(have) >= m never becomes true, leaving result at its initial value of zero, which correctly reflects the absence of a qualifying window. The use of defaultdict(int) ensures that attempts to decrement a non-existent key never raise a KeyError, because the key is created with a default count of zero before the decrement.

Performance Optimizations

The implementation achieves constant-time updates for both the window sum and the distinct-count tracking. Adjusting the sum involves a single addition or subtraction per iteration, while the frequency map updates consist of dictionary lookups and modifications that are O(1) on average. Deleting a key when its count reaches zero prevents the map from growing unnecessarily, which keeps the memory footprint proportional to the number of distinct values inside the current window rather than the total number of processed elements. By avoiding recomputation of the sum or distinct count from scratch for each window position, the method processes the entire list in a single linear pass, delivering high throughput even for large inputs.

Imagine a long train made of many colorful toy cars. Each car has a number on it. This code is like sliding a special frame that keeps only k cars in view at one time. As the frame moves from the left side of the train to the right side, one car leaves from the back and a new car enters at the front.

Inside the frame, the code uses a magic box to count how many of each kind of car are sitting there. The rule is that the frame wants to find a group of cars that are different enough to satisfy a goal called m. If the frame holds at least m unique types of cars, it adds up all the numbers painted on them.

The code works by looking at every possible group of cars that fits in the frame. For every group, it checks if there are enough different kinds. If the sum of the numbers in that group is bigger than the best sum found so far, it saves that larger pile as the new champion. It keeps sliding the frame until it reaches the very end of the train, constantly watching the total and updating the champion pile whenever a better one appears.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java		C++			Python	TS
	WalkCCC	Java		C++			Python
	leetcode.ca	Java		C++	C#	Go	Python	TS
	Progiez	Java		C++			Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality