LeetCode 2555 - Maximize Win From Two Segments

LeetCode Problem 2555

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window

Solution

Problem Understanding

The problem gives us a sorted array prizePositions, where each value represents the position of a prize on the X-axis. Multiple prizes may exist at the same position. We are also given an integer k.

We may choose exactly two segments on the number line. Each segment must have length k, meaning if the left endpoint is x, then the right endpoint must be x + k. A prize is collected if its position lies inside at least one of the two segments, including the endpoints.

Our goal is to maximize the total number of collected prizes.

A key detail is that the array is already sorted. This immediately suggests that contiguous ranges in the array correspond to contiguous regions on the number line. Since the constraints allow up to 10^5 prizes, any algorithm worse than roughly O(n log n) or O(n) will likely be too slow.

Another important observation is that the segments may overlap. We are not required to keep them disjoint. However, overlapping segments are usually not beneficial unless the optimal windows naturally intersect.

The input constraints also tell us several important things:

• prizePositions.length <= 10^5, so quadratic approaches are too slow.
• Positions can be as large as 10^9, which means we cannot use coordinate compression grids or counting arrays indexed by position.
• The array is already sorted, which strongly hints toward sliding window or binary search techniques.

Several edge cases are important:

• k = 0, meaning each segment can cover only a single coordinate.
• Many duplicate positions.
• All prizes fitting inside one segment.
• The best two segments overlapping.
• Very large gaps between positions.

The problem asks only for the maximum count, not the actual segment endpoints.

Approaches

Brute Force Approach

A brute force solution would try every possible segment placement for the first segment and every possible segment placement for the second segment.

Because the array is sorted, we could define a segment by choosing a starting index i, then finding the furthest index j such that:

prizePositions[j] - prizePositions[i] <= k

This gives one valid segment. We could then try every second segment similarly and compute the union of covered prizes.

The issue is that there are O(n) possible segments, and comparing every pair leads to O(n^2) combinations. Even if each comparison is efficient, this becomes too slow for n = 10^5.

The brute force method is correct because it explicitly checks all possible segment pairs, but it is computationally infeasible.

Optimal Approach

The key insight is that once we know the best segment ending before some position, we can combine it with the current segment.

Suppose we use a sliding window to determine, for every right endpoint r, how many prizes can be covered by a segment ending at r.

Then we maintain:

best[i] = maximum prizes collectible using one segment among indices [0..i]

Now when considering a segment covering indices [left, right], we know:

• Current segment contributes:

right - left + 1

• The best non-overlapping segment before left contributes:

best[left - 1]

Combining them gives the optimal two-segment answer.

This works efficiently because both the sliding window and prefix maximum array can be maintained in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Tries every pair of valid segments
Optimal	O(n)	O(n)	Sliding window with prefix best array

Algorithm Walkthrough

1. Initialize two pointers, left and right, for a sliding window.

The window represents prizes that can be covered by a single segment of length k. Because the array is sorted, if:

prizePositions[right] - prizePositions[left] <= k

then all prizes between those indices fit inside one valid segment. 2. Expand the window by moving right from left to right.

For each new right, we attempt to include it in the current segment. 3. Shrink the window while it becomes invalid.

If:

prizePositions[right] - prizePositions[left] > k

then the segment is too long, so we increment left until the window becomes valid again. 4. Compute the current window size.

Once the window is valid:

current_window = right - left + 1

This represents the number of prizes covered by one segment ending at right. 5. Maintain a prefix maximum array.

Define:

best[i]

as the maximum number of prizes collectible using one segment among indices 0..i.

Update:

best[right] = max(best[right - 1], current_window)

6. Combine the current segment with a previous segment.

The current segment covers indices [left, right].

Any previous segment must end before left to avoid double counting.

Therefore:

previous_best = best[left - 1]

if left > 0, otherwise 0.

Total prizes collected:

current_window + previous_best

7. Track the maximum total over all windows.

Update the answer each iteration.

Why it works

The sliding window guarantees that every valid segment is considered exactly once as a contiguous range in the sorted array.

The best array guarantees that for every possible second segment, we already know the optimal first segment that ends before it begins. Since the array is processed left to right, this information is always available when needed.

Because every possible valid segment appears as some sliding window state, and because we optimally combine it with the best earlier segment, the algorithm always finds the global optimum.

Python Solution

from typing import List

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)

        best = [0] * n

        left = 0
        answer = 0

        for right in range(n):
            while prizePositions[right] - prizePositions[left] > k:
                left += 1

            current_window = right - left + 1

            if right == 0:
                best[right] = current_window
            else:
                best[right] = max(best[right - 1], current_window)

            previous_best = best[left - 1] if left > 0 else 0

            answer = max(answer, current_window + previous_best)

        return answer

The implementation follows the algorithm directly.

The variable left tracks the beginning of the current valid window, while right iterates through the array.

The while loop maintains the invariant that the current window always satisfies:

prizePositions[right] - prizePositions[left] <= k

The variable current_window stores the number of prizes covered by the current segment.

The array best stores prefix maximums. At every index, it records the largest valid segment found so far. This allows constant time lookup for the best segment before the current window.

Finally, the algorithm combines the current segment with the best earlier segment and updates the answer.

Go Solution

func maximizeWin(prizePositions []int, k int) int {
	n := len(prizePositions)

	best := make([]int, n)

	left := 0
	answer := 0

	for right := 0; right < n; right++ {
		for prizePositions[right]-prizePositions[left] > k {
			left++
		}

		currentWindow := right - left + 1

		if right == 0 {
			best[right] = currentWindow
		} else {
			best[right] = max(best[right-1], currentWindow)
		}

		previousBest := 0
		if left > 0 {
			previousBest = best[left-1]
		}

		answer = max(answer, currentWindow+previousBest)
	}

	return answer
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation closely mirrors the Python version.

Slices are used instead of Python lists. Since Go does not provide a built-in max function for integers, a helper function is implemented manually.

Integer overflow is not a concern because the maximum number of prizes is only 10^5, well within Go's integer range.

Worked Examples

Example 1

Input:

prizePositions = [1,1,2,2,3,3,5]
k = 2

Step-by-step Trace

right	left	Window Values	Window Size	best[right]	previous_best	answer
0	0	[1]	1	1	0	1
1	0	[1,1]	2	2	0	2
2	0	[1,1,2]	3	3	0	3
3	0	[1,1,2,2]	4	4	0	4
4	0	[1,1,2,2,3]	5	5	0	5
5	0	[1,1,2,2,3,3]	6	6	0	6
6	2	[2,2,3,3,5]	5	6	2	7

Final answer:

7

The optimal combination is:

• First segment covers the two 1s.
• Second segment covers [2,2,3,3,5].

Together they cover all prizes.

Example 2

Input:

prizePositions = [1,2,3,4]
k = 0

Step-by-step Trace

right	left	Window Values	Window Size	best[right]	previous_best	answer
0	0	[1]	1	1	0	1
1	1	[2]	1	1	1	2
2	2	[3]	1	1	1	2
3	3	[4]	1	1	1	2

Final answer:

2

Since each segment can cover only one coordinate, the best possible result is collecting two prizes.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves at most n times
Space	O(n)	Prefix maximum array stores n values

The sliding window is linear because both left and right only move forward. No element is processed more than twice.

The additional memory comes from the best array, which stores the best segment size up to each index.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximizeWin([1,1,2,2,3,3,5], 2) == 7  # all prizes covered
assert sol.maximizeWin([1,2,3,4], 0) == 2  # each segment covers one point

# Single prize
assert sol.maximizeWin([5], 10) == 1  # only one prize exists

# All prizes same position
assert sol.maximizeWin([2,2,2,2], 0) == 4  # one segment already covers all

# Large k covers everything
assert sol.maximizeWin([1,5,10,15], 100) == 4  # entire array fits in one segment

# Two clearly separated groups
assert sol.maximizeWin([1,2,3,100,101,102], 2) == 6  # use one segment per cluster

# Overlapping optimal windows
assert sol.maximizeWin([1,2,3,4,5], 2) == 5  # overlap still allows full coverage

# Many duplicates
assert sol.maximizeWin([1,1,1,2,2,3,10,10], 1) == 8  # two segments cover all

# Sparse positions
assert sol.maximizeWin([1,10,20,30], 5) == 2  # each segment covers one prize

# Window shift edge case
assert sol.maximizeWin([1,2,4,5,6], 2) == 5  # best split found after shrinking

# Two segments needed
assert sol.maximizeWin([1,2,3,50,51,52], 1) == 4  # each segment covers two prizes

Test Summary

Test	Why
[1,1,2,2,3,3,5], k=2	Validates standard overlapping coverage
[1,2,3,4], k=0	Tests zero-length segments
[5], k=10	Smallest input size
[2,2,2,2], k=0	Handles duplicates correctly
[1,5,10,15], k=100	One segment can cover everything
[1,2,3,100,101,102], k=2	Two distant clusters
[1,2,3,4,5], k=2	Overlapping windows
[1,1,1,2,2,3,10,10], k=1	Heavy duplication
[1,10,20,30], k=5	Sparse coordinates
[1,2,4,5,6], k=2	Tests sliding window movement
[1,2,3,50,51,52], k=1	Requires optimal split

Edge Cases

One important edge case is when k = 0. In this scenario, each segment can cover only a single coordinate. A naive implementation might incorrectly assume every window has size at least two if indices are adjacent. The sliding window condition correctly handles this because only equal values remain inside the window.

Another critical case is when many prizes share the same position. For example:

[2,2,2,2]

Even with k = 0, one segment can collect all prizes because they occupy the same coordinate. The implementation handles this naturally because the window condition depends on coordinate difference, not index difference.

A third important case occurs when all prizes already fit inside one segment. A buggy implementation might unnecessarily force two disjoint segments and undercount the answer. This solution avoids that problem because the second segment may contribute zero additional prizes, while the first segment alone can already cover the entire array.

Another subtle case involves overlapping optimal windows. Since overlapping is allowed, the algorithm must not artificially forbid intersections. The implementation only prevents double counting through the best[left - 1] combination logic, while still allowing the actual segment intervals themselves to overlap geometrically on the number line.