Watch 10 video solutions for Maximize Win From Two Segments, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by codingMohan has 2,547 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |