Maximize Win From Two Segments solution and explanation
9 more videos on this problem
Maximize Win From Two Segments | Biweekly Contest 97 | LeetcodecodingMohan · 16:08 · 2K views
Maximize Win From Two Segments || leetcode Biweekly 97 || Leetcode MediumBinaryMagic · 16:27 · 2K views
2555. Maximize Win From Two Segments | LeetCodeDeep Tech · 17:27 · 1K views
2555. Maximize Win From Two Segments (Leetcode Medium)Programming Live with Larry · 18:22 · 1K views
LeetCode Biweekly Contest 97 | 2555 : Maximize Win From Two Segments Solution | Newton SchoolFly with Coding | Newton School · 18:13 · 1K views
2555. Maximize Win From Two Segments | Leetcode BiWeekly contest 97 | Sliding Window approachTech Courses · 16:10 · 1K views
【每日一题】LeetCode 2555. Maximize Win From Two SegmentsHuifeng Guan · 17:23 · 479 views
Maximize Win From Two Segments | Leetcode BiWeekly Contest 97 | Que-3 | Two Pointer, Prefix Sum |C++Explore with Gyani · 21:38 · 252 views
2555. Maximize Win From Two Segments | Medium | Leetcode | Asmr Programming.Optimization · 12:13 · 110 views
Maximize Win From Two Segments - LeetCode Biweekly 97LeetCode Україна · 19:03 · 71 views
The problem
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.
- For example if
k = 2, you can choose segments[1, 3]and[2, 4], and you will win any prize i that satisfies1 <= prizePositions[i] <= 3or2 <= 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 <= 109prizePositionsis sorted in non-decreasing order.
Approach overview
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 1: Sliding Window Technique
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.
def maximizeWin(prizePositions, k):
n = len(prizePositions)
left, right = 0, 0
maxPrizes = 0
currentSegment = [0] * n
while right < n:
while right < n and prizePositions[right] - prizePositions[left] <= k:
right += 1
currentSegment[left] = right - left
left += 1
max_single = max(currentSegment)
maxPrizes = max_single
currentSegment[left - 1] = 0
for i in range(1, n):
maxPrizes = max(maxPrizes, currentSegment[i] + currentSegment[i - 1])
return maxPrizes
# Example usage
print(maximizeWin([1, 1, 2, 2, 3, 3, 5], 2))function maximizeWin(prizePositions, k) {
let n = prizePositions.length;
let left = 0, right = 0;
let maxPrizes = 0;
let currentSegment = Array(n).fill(0);
while (right < n) {
while (right < n && prizePositions[right] - prizePositions[left] <= k) {
right++;
}
currentSegment[left] = right - left;
left++;
}
let max_single = Math.max(...currentSegment);
maxPrizes = max_single;
currentSegment[left - 1] = 0;
for (let i = 1; i < n; i++) {
maxPrizes = Math.max(maxPrizes, currentSegment[i] + currentSegment[i - 1]);
}
return maxPrizes;
}
// Example usage
console.log(maximizeWin([1, 1, 2, 2, 3, 3, 5], 2));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.
Time Complexity: O(n), as we iterate through the list using two pointers.
Space Complexity: O(n), due to the 'currentSegment' array.
Approach 2: Two-Pointer Range Combination
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.
import java.util.*;
public class MaximizeWin {
public int maximizeWin(int[] prizePositions, int k) {
int n = prizePositions.length;
int left = 0, right = 0;
int maxPrizes = 0;
int[] currentSegment = new int[n];
while (right < n) {
while (right < n && prizePositions[right] - prizePositions[left] <= k) {
right++;
}
currentSegment[left] = right - left;
left++;
}
int max_single = Arrays.stream(currentSegment).max().orElse(0);
maxPrizes = max_single;
currentSegment[left - 1] = 0;
for (int i = 1; i < n; i++) {
maxPrizes = Math.max(maxPrizes, currentSegment[i] + currentSegment[i - 1]);
}
return maxPrizes;
}
public static void main(String[] args) {
MaximizeWin solution = new MaximizeWin();
System.out.println(solution.maximizeWin(new int[] {1, 1, 2, 2, 3, 3, 5}, 2));
}
}#include <vector>
#include <algorithm>
int maximizeWin(std::vector<int>& prizePositions, int k) {
int n = prizePositions.size();
int left = 0, right = 0;
int maxPrizes = 0;
std::vector<int> currentSegment(n, 0);
while (right < n) {
while (right < n && prizePositions[right] - prizePositions[left] <= k) {
right++;
}
currentSegment[left] = right - left;
left++;
}
int max_single = *std::max_element(currentSegment.begin(), currentSegment.end());
maxPrizes = max_single;
currentSegment[left - 1] = 0;
for (int i = 1; i < n; i++) {
maxPrizes = std::max(maxPrizes, currentSegment[i] + currentSegment[i - 1]);
}
return maxPrizes;
}
// Example usage
// std::vector<int> prizes = {1, 1, 2, 2, 3, 3, 5};
// int result = maximizeWin(prizes, 2);The Java solution mimics the structure of the two-pointer approach seen in Python and C++. It iterates through the prize positions with two pointers to check coverage, storing intermediate results in an array. Post this, it uses a secondary scan to assess how combinations of these can further maximize the coverage with two overlapping segments.
Both time and space complexities are O(n), with linear passes and an auxiliary array to hold segment coverage data.
Approach 3: 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.
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.
function maximizeWin(prizePositions: number[], k: number): number {
const n = prizePositions.length;
const f: number[] = Array(n + 1).fill(0);
let ans = 0;
const search = (x: number): number => {
let left = 0;
let right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (prizePositions[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
for (let i = 1; i <= n; ++i) {
const x = prizePositions[i - 1];
const j = search(x - k);
ans = Math.max(ans, f[j] + i - j);
f[i] = Math.max(f[i - 1], i - j);
}
return ans;
}func maximizeWin(prizePositions []int, k int) (ans int) {
n := len(prizePositions)
f := make([]int, n+1)
for i, x := range prizePositions {
j := sort.Search(n, func(h int) bool { return prizePositions[h] >= x-k })
ans = max(ans, f[j]+i-j+1)
f[i+1] = max(f[i], i-j+1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), as we iterate through the list using two pointers. |
| Two-Pointer Range Combination | Both time and space complexities are O(n), with linear passes and an auxiliary array to hold segment coverage data. |
| Dynamic Programming + Binary Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximize Win From Two Segments easy or hard?
Maximize Win From Two Segments is rated Medium difficulty on LeetCode. The challenge comes from combining two optimal segments without overlap. Recognizing that sliding window plus prefix optimization reduces the problem to a linear scan is the key insight.
Maximize Win From Two Segments Python/Java solution
Python solutions usually implement the sliding window technique because it provides a clean O(n) implementation with two pointers and a prefix array. Java and C++ solutions often follow the same logic or use binary search to compute segment ranges before combining them.
How to solve Maximize Win From Two Segments in O(n)?
Use a sliding window to compute the number of prizes covered by each valid segment while scanning the array once. Maintain a prefix array storing the best segment size seen so far. For each window ending at index r, combine its size with the best segment that ends before its starting point. This guarantees the maximum total prizes in linear time.
What is the best approach for Maximize Win From Two Segments?
The sliding window approach is the most efficient and commonly expected solution. It scans the sorted prizePositions array with two pointers to maintain a valid segment of length k. A prefix array tracks the best segment seen so far so the current window can be combined with a previous one. This produces an optimal O(n) time solution.
Is Maximize Win From Two Segments asked at Google/Amazon/Meta?
Problems combining sliding window with prefix optimization are common in interviews at companies like Amazon, Google, and Meta. Variants involving maximum coverage, interval selection, or two non-overlapping windows appear frequently in coding interviews.
What data structure is used in Maximize Win From Two Segments?
The core solution relies on arrays and the two-pointer technique. A prefix maximum array stores the best segment length found so far, while the sliding window controls the current valid range. Some implementations also use binary search to locate the end of each segment.
What is the time complexity of Maximize Win From Two Segments?
The optimal sliding window solution runs in O(n) time with O(n) extra space for prefix maximum tracking. Each pointer moves at most n times, so the array is processed in a single pass. A binary search based approach takes O(n log n) time.