#2555

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximize Win From Two Segments

Maximize the total prizes by choosing two segments of length k on a sorted line of prize positions efficiently using binary search.

array binary search sliding window

Problem Statement

You are given a sorted array prizePositions representing prizes along the X-axis. Each element indicates the position of a prize, and multiple prizes may share the same position. An integer k specifies the length of segments you can select.

Select exactly two segments of length k along the X-axis. You collect all prizes covered by at least one segment. Segments can overlap. Return the maximum total number of prizes obtainable by choosing the two segments optimally.

Examples

Example 1

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

Output: 7

In this example, you can win all 7 prizes by selecting two segments [1, 3] and [3, 5].

Example 2

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

Output: 2

For this example, one choice for the segments is [3, 3] and [4, 4], and you will be able to get 2 prizes.

Constraints

1 <= prizePositions.length <= 105
1 <= prizePositions[i] <= 109
0 <= k <= 109
prizePositions is sorted in non-decreasing order.

Solution Approach

Use Sliding Window for Single Segment

Start by computing the number of prizes within each segment of length k using a sliding window approach. This helps understand coverage for one interval before adding the second segment.

Precompute Maximum from Right

Store the maximum number of prizes obtainable from the right for each index. This allows you to combine each left segment with the best possible right segment efficiently.

Combine with Binary Search Over Answer

Iterate through possible left segments and use precomputed right segment values to find the optimal combination. Binary search ensures you efficiently find the farthest segment start that can form a valid pair, maximizing the total prize count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) with sliding windows and precomputation, while binary search ensures efficient selection of segment pairs. Space complexity is O(n) for storing maximums from the right.

What Interviewers Usually Probe

Are you considering overlapping segments correctly?
Have you tried computing maximum prizes from the right to pair efficiently?
Can you optimize selection with binary search over segment endpoints?

Common Pitfalls or Variants

Common pitfalls

Forgetting segments can overlap and double-counting prizes.
Not precomputing maximum prizes from the right, leading to inefficient O(n^2) solutions.
Misapplying sliding window logic when k = 0 or segments touch endpoints.

Follow-up variants

Maximize win with three segments of fixed length.
Change segment lengths dynamically for each selection.
Prizes are on a 2D plane with axis-aligned segments.

FAQ

What is the main approach for Maximize Win From Two Segments?

Use a sliding window to count prizes in segments and binary search to combine two segments for maximum coverage.

Can segments overlap in this problem?

Yes, segments can intersect, and prizes in the overlap should be counted only once for total maximization.

How do you handle large prizePositions arrays efficiently?

Sliding window with precomputed maximums from the right ensures O(n) iteration, avoiding O(n^2) checks.

Why is binary search needed for this problem?

Binary search helps quickly find the farthest valid right segment to pair with a left segment, maximizing prizes.

How does GhostInterview solve the pattern of two segments?

It automatically computes optimal single and paired segments using the sliding window plus binary search pattern, showing exact prize counts.

terminal

Solution

Solution 1: Dynamic Programming + Binary Search

We define $f[i]$ as the maximum number of prizes that can be obtained by selecting a segment of length $k$ from the first $i$ prizes. Initially, $f[0] = 0$. We define the answer variable as $ans = 0$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        f = [0] * (n + 1)
        ans = 0
        for i, x in enumerate(prizePositions, 1):
            j = bisect_left(prizePositions, x - k)
            ans = max(ans, f[j] + i - j)
            f[i] = max(f[i - 1], i - j)
        return ans

Continue Practicing

#2528 maximize the minimum powered city #2411 smallest subarrays with maximum bitwise or #2398 maximum number of robots within budget