There are some prizes on the X-axis. You are given an integer array prizePositions that is sorted in non-decreasing order, where prizePositions[i] is the position of the ith prize. There could be different prizes at the same position on the line. You are also given an integer k.
You are allowed to select two segments with integer endpoints. The length of each segment must be k. You will collect all prizes whose position falls within at least one of the two selected segments (including the endpoints of the segments). The two selected segments may intersect.
k = 2, you can choose segments [1, 3] and [2, 4], and you will win any prize i that satisfies 1 <= prizePositions[i] <= 3 or 2 <= prizePositions[i] <= 4.Return the maximum number of prizes you can win if you choose the two segments optimally.
Example 1:
Input: prizePositions = [1,1,2,2,3,3,5], k = 2 Output: 7 Explanation: 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 Explanation: For this example, one choice for the segments is[3, 3]and[4, 4],and you will be able to get2prizes.
Constraints:
1 <= prizePositions.length <= 1051 <= prizePositions[i] <= 1090 <= k <= 109 prizePositions is sorted in non-decreasing order.In #2555 Maximize Win From Two Segments, you are given sorted prize positions and a segment length k. The goal is to choose two non-overlapping segments of length k that maximize the number of prizes collected. Since the positions are sorted, this problem can be efficiently solved using a sliding window combined with prefix optimization.
First, use a two-pointer sliding window to determine how many prizes fall within a segment of length k. As the right pointer expands, move the left pointer while positions[right] - positions[left] > k. This gives the number of prizes covered by the current segment.
To handle two segments, maintain a prefix best array that stores the maximum prizes obtainable from any segment ending before the current window. At each step, combine the current window's prize count with the best previous segment to maximize the result.
This approach works in O(n) time using two pointers, with O(n) additional space for prefix tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window + Prefix Best | O(n) | O(n) |
| Binary Search + Prefix Optimization | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Try solving the problem for one interval.
Using the solution with one interval, how can you combine that with a second interval?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this are common in technical interviews because they test sliding window techniques, greedy thinking, and prefix optimization. Variations of this pattern appear in interviews at top tech companies.
Arrays and the two-pointer technique are the most important tools for this problem. A prefix array is also used to track the best segment found so far, enabling efficient combination of two segments.
Yes, binary search can be used to find the farthest index that fits within the segment length k for each starting position. Combined with prefix maximum tracking, this leads to an O(n log n) solution.
The optimal approach uses a sliding window with two pointers and a prefix maximum array. The window calculates how many prizes fit in a segment of length k, while the prefix array stores the best result from previous segments. This allows combining two non-overlapping segments efficiently in O(n) time.