Abstract / Summary

Find the highest sum of a subarray that contains at most k distinct numbers.

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 64% (100k+ submissions).

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 computes the maximum possible score of a subarray that must contain a fixed index k. The score of a subarray is defined as the product of its length and the minimum element within that subarray. The algorithm first builds an auxiliary array that records, for every position, the smallest value seen when expanding from the mandatory index k outward. It then expands a window around k while maintaining the current minimum on each side, updating the best score whenever a larger width is found. The approach works in a single pass over the input after the auxiliary array is prepared, guaranteeing that all candidate subarrays are examined without redundant recomputation.

Building the minimum-to-k array

The first phase creates an array low where low[i] holds the minimum element between positions i and k (inclusive). Two sweeps are performed: one moving left from k to the start of the list, and another moving right from k+1 to the end.

low  = [ inf ] * len(nums)
have = nums[k]
for i in range(k, -1, -1):
    have = min(have, nums[i])
    low[i] = have

have = nums[k]
for j in range(k + 1, len(nums)):
    have = min(have, nums[j])
    low[j] = have

The leftward sweep updates have with the smallest value encountered so far, storing it at each index. The rightward sweep does the same for positions to the right of k. After these loops, low[i] correctly reflects the minimum value that would be present in any subarray extending from i to k.

Initial result candidate

Before entering the main expansion loop, the algorithm considers the whole array as a possible subarray. The score for the entire array is computed using the smallest of the two extreme minima stored in low.

result = len(low) * min(low[0], low[-1])

This handles the edge case where the optimal subarray spans the full length of nums, ensuring that the final answer is never smaller than this baseline.

Expanding the window around k

Two pointers, i and j, start at the mandatory index k. The loop continues while either pointer can move outward. Inside the loop, the algorithm first collapses any consecutive positions that share the same minimum value, effectively skipping over flat regions that would not improve the score.

while i > 0 or j < len(low) - 1:
    while i > 0     and low[i] == low[i - 1]:
        i -= 1
    while j < k - 1 and low[j] == low[j + 1]:
        j += 1

By moving past equal minima, the code avoids unnecessary width calculations for subarrays that would yield identical scores, thereby reducing the number of iterations.

Updating the best score

After the pointers have been adjusted, the current window width and the minimum value at its boundaries are used to compute a candidate score. The result is updated if this candidate exceeds the previous best.

width  = j - i + 1
result = max(result, width * min(low[i], low[j]))

The use of min(low[i], low[j]) correctly captures the smallest element inside the current window, because low[i] and low[j] already represent the minima from each side to k.

Handling borders

When one side of the window reaches the array boundary, the algorithm forces expansion on the opposite side. This ensures that all subarrays that include k and extend to the ends are examined.

if i == 0:
    j += 1
    continue
if j == len(low) - 1:
    i -= 1
    continue

These conditions gracefully handle the edge cases where the leftmost or rightmost index is reached, preventing out-of-range accesses while still allowing the window to grow.

Choosing the side to expand

If neither pointer is at a border, the algorithm decides which side to extend based on the next potential minimum values. The side with the larger upcoming minimum is chosen, because extending that side is more likely to increase the product of width and minimum.

if low[i - 1] > low[j + 1]:
    i -= 1
else:
    j += 1

This greedy choice steers the expansion toward regions that preserve a higher minimum, thereby focusing the search on promising candidates without exhaustive enumeration.

Performance optimizations

The construction of low uses two linear sweeps, each updating a running minimum in constant time per element. This eliminates the need for nested loops that would recompute minima for every possible subarray.

During the expansion phase, the inner loops that skip over equal minima compress stretches of identical values into a single step. By doing so, the algorithm reduces the number of iterations proportional to the number of distinct minima rather than the total length of the array.

The decision to extend the side with the larger next minimum avoids unnecessary exploration of subarrays that would quickly drop the minimum value, effectively pruning the search space. Combined with the border checks, this results in a tight traversal that visits each index at most a constant number of times.

Overall, the method achieves a linear-time execution pattern, processing the input array a fixed number of times and performing only simple arithmetic and comparison operations in each step. This makes it well-suited for large inputs where a naïve quadratic approach would be prohibitive.

Imagine you have a long line of numbered building blocks sitting in a row on the floor. You choose one stone in the middle to be your special starting point. The goal is to stretch out a rectangle as wide as you can while keeping the numbers inside the rectangle big and tall.

First, the code walks to the left and then to the right from your special starting stone. As it travels, it keeps track of the smallest number it has seen so far. Think of this like keeping a record of the shortest friend in a group, because the shortest friend determines how tall the whole group can stand.

After measuring all the possible heights in both directions, the code starts growing the rectangle. It looks at the numbers on both edges of the current rectangle to see which side has a taller friend waiting next in line. It always picks the taller side to make the rectangle wider, because that keeps the area as large as possible. If the numbers are the same, it stretches out as far as it can on both sides to grab more space.

As the rectangle grows, it constantly checks how much space it covers by multiplying the width by the height of the smallest number it included. Every time it finds a new, bigger total, it remembers that as the new best score. It continues doing this until it reaches the very ends of the line of blocks.

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	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	MacJim	C++
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
MacJim	C++
suxrobGM	C#
wisdompeak	C++

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