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.
Problem Overview: You are given a sorted array prizePositions where each value represents the location of a prize on a number line. You can choose two segments of length k. Each segment collects all prizes within its range. The goal is to place both segments so the total number of collected prizes is maximized.
Approach 1: Sliding Window Technique (O(n) time, O(n) space)
This approach uses a classic sliding window to compute how many prizes each valid segment can capture. Maintain two pointers left and right while scanning the sorted array. Expand right and shrink left whenever the distance between positions exceeds k. The window size right - left + 1 gives the number of prizes collected by a segment ending at right. Track the best segment seen so far using a prefix array so you can combine the current segment with the best non-overlapping one before it. This method works in a single pass and guarantees the optimal answer because the array is sorted and every valid segment is evaluated exactly once.
Approach 2: Two-Pointer Range Combination (O(n log n) time, O(n) space)
Another way is to compute the maximum prizes covered by a segment starting at each index, then combine two non-overlapping segments. For each starting index i, use binary search to find the furthest position where prizePositions[j] - prizePositions[i] ≤ k. The segment size becomes j - i + 1. Store these values and build a suffix or prefix maximum array that tracks the best segment available after each index. When iterating through possible first segments, combine their size with the best second segment starting after the current range. Binary search keeps each range query efficient while the prefix/suffix array ensures quick combination.
Recommended for interviews: The sliding window solution is the one interviewers usually expect. It runs in O(n) time and demonstrates strong understanding of two-pointer patterns on sorted arrays. The binary search variation shows solid problem-solving as well, but the sliding window approach highlights better optimization skills and cleaner reasoning.
The sliding window technique allows us to efficiently find the number of prizes covered by a segment of length k. We slide two windows over the prizes array to maximize the count of covered prizes for two segments. This approach ensures that we consider overlapping segments and optimizes coverage by combining counts from both segments.
The code utilizes a sliding window approach to calculate how many prizes can be covered by a segment starting from each position. Then it checks the maximum number of prizes collected in two segments, allowing potential overlaps. Two iterations are used: the first to populate how many prizes can be collected starting from each point, and the second to calculate the maximum number of prizes using two overlapping segments.
Python
JavaScript
Time Complexity: O(n), as we iterate through the list using two pointers.
Space Complexity: O(n), due to the 'currentSegment' array.
This approach leverages two pointers to calculate the number of prizes within a segment of length k and explores the optimal way to merge two segments. It checks the combination of ranges to exploit overlap and maximize the number of prizes captured by two non-disjoint segments.
The C++ solution uses a similar approach to the two-pointer sliding window, checking how many prizes fit in a single segment and then calculating how two would maximize the prize count. A combination of elements using cumulative array storage helps efficiently determine the maximum number of segments combining.
The C++ code runs in O(n) due to the linear pass for both calculating the segment coverage and the second pass to find the optimal two segments. The space complexity is O(n) for storing intermediate segment calculations.
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.
Next, we enumerate the position x of each prize, and use binary search to find the leftmost prize index j such that prizePositions[j] geq x - k. At this point, we update the answer ans = max(ans, f[j] + i - j), and update f[i] = max(f[i - 1], i - j).
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of prizes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), as we iterate through the list using two pointers. |
| Two-Pointer Range Combination | The C++ code runs in O(n) due to the linear pass for both calculating the segment coverage and the second pass to find the optimal two segments. The space complexity is O(n) for storing intermediate segment calculations. |
| Dynamic Programming + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique | O(n) | O(n) | Best choice when the array is sorted and you want a linear scan using two pointers |
| Two-Pointer Range Combination with Binary Search | O(n log n) | O(n) | Useful when computing ranges independently with binary search before combining segments |
Maximize Win From Two Segments | Biweekly Contest 97 | Leetcode • codingMohan • 2,547 views views
Watch 9 more video solutions →Practice Maximize Win From Two Segments with our built-in code editor and test cases.
Practice on FleetCode