Abstract / Summary

Choose two non overlapping segments to maximize the total value from a list of integers.

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 38% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• 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 implementation solves the problem of selecting two non-overlapping intervals of length k on a sorted list of prize positions so that the total number of collected prizes is maximized. It proceeds in three logical phases: counting how many prizes each possible interval can capture, building a suffix-maximum array that records the best interval that can start at or after any index, and finally combining a left interval with the best possible right interval.

Counting prizes per interval

For every starting position the code determines the farthest index that still lies within distance k. Because the input list is sorted, a binary search (bisect_right) finds this boundary in logarithmic time. The difference between the boundary index and the current index yields the number of prizes that can be collected if the interval starts at that position.

collect = []
for i, left in enumerate(prizePositions):
    right = left + k
    pos = bisect_right(prizePositions, right)
    collect.append(pos - i)

The collect list therefore holds, at each index i, the size of the interval [prizePositions[i], prizePositions[i] + k].

Building the suffix-maximum array

To avoid a quadratic scan when pairing intervals, the algorithm constructs an auxiliary array best. Traversing the indices in reverse, best[i] stores the maximum value among collect[i] and all later entries. This enables constant-time lookup of the best possible right-hand interval for any left interval.

best = [0] * (size + 1)
for i in reversed(range(size)):
    best[i] = max(best[i + 1], collect[i])

The extra element at size guarantees that best[i + one] is always a valid index, even when the left interval consumes the remainder of the list.

Combining two intervals

The final pass iterates over every possible left interval. For each start index i, the number of prizes collected by the left interval is one = collect[i]. The index immediately after this interval is i + one. The pre-computed best array supplies the optimal right interval that begins at or after that point (two = best[i + one]). The sum one + two represents the total prizes for this particular split, and the maximum over all splits is retained.

result = 0
for i in range(size):
    one = collect[i]
    two = best[i + one]
    result = max(result, one + two)

The function returns result, the maximum achievable prize count using two disjoint intervals of length k.

Edge-case handling

When the input list is empty, size becomes zero. The loops that populate collect, best, and the final combination all iterate over empty ranges, leaving result at its initial value of 0, which correctly reflects that no prizes can be collected.

If k is zero, each interval can only contain the prize at its starting position. The binary search then returns the index of the first element greater than the start value, making collect[i] equal to 1 for every i. The suffix-maximum array consequently contains only 1s, and the combination step correctly yields a total of 2 when at least two prizes exist, or 1 when only a single prize is present.

When the distance between consecutive prizes exceeds k, the binary search always stops at the next element, again producing collect[i] = 1. The algorithm still correctly identifies the two best isolated prizes.

If k is larger than the span of all positions, the binary search for the first element returns the length of the list, so collect[0] equals size and all subsequent collect entries are decreasing counts. The suffix-maximum array captures the largest possible interval, and the combination step correctly chooses the single interval covering all prizes with the second interval contributing zero, yielding the optimal total.

Performance optimizations

The code leverages the sorted nature of prizePositions by using bisect_right, which reduces the interval-counting step from a potential linear scan per start to a logarithmic search. The creation of the best suffix array transforms what would be a nested search for the optimal right interval into a constant-time lookup, collapsing the overall pairing phase to linear time. Pre-allocating the best list with the exact required size avoids dynamic resizing during the reverse pass. Together, these choices keep the total work proportional to n log n for n prizes while using only a few auxiliary arrays of size n.

Imagine you are looking at a long path covered in shiny gold toys. Each toy is at a different spot on the ground, and you have two special nets to scoop them up. Each net is a certain length, and you want to place them so you can grab the most toys possible without them overlapping.

The first part of the code looks at every toy and imagines placing a net starting at that spot. It figures out how many toys would fit inside one net of that length and keeps a little list of those counts.

The second part of the code creates a helper list that acts like a cheat sheet. It works backward from the very last toy to the first one, always remembering the biggest number of toys seen so far. This makes it really easy to look ahead and see where the best toy collection starts after finishing the first net.

The final part of the code is like a game of strategy. It pretends to place the first net starting at every single possible position. For each position, it takes the number of toys grabbed by that net and adds it to the biggest group of toys that could be grabbed by a second net placed later on the path. By checking every combination this way, the code finds the very best way to position the nets to gather the biggest pile of toys.

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

Time: loglinear
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	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	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