Maximize Win From Two Segments — Problem & Solution
Maximize Win From Two Segments solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize Win From Two Segments is a medium coding problem on arrays, binary search and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Prizes lie on the number line. prizePositions lists their positions in non-decreasing order; several prizes may share a position.
You may choose two segments with integer endpoints, each of length exactly k — a segment [l, l + k] collects every prize whose position lies within it, ends included. The segments may overlap, and a prize inside both is still collected once.
Return the maximum number of prizes you can collect.
Example 1
Input: prizePositions = [1,2,2,4,7,8,8,12], k = 2
Output: 6
Explanation: `[1,3]` collects 1, 2, 2 and `[7,9]` collects 7, 8, 8.
Example 2
Input: prizePositions = [3,3,3], k = 0
Output: 3
Explanation: The single point segment `[3,3]` already holds all three prizes.
Example 3
Input: prizePositions = [1,5,9,13], k = 1
Output: 2
Explanation: Each segment can reach only one prize.
Constraints
1 <= prizePositions.length <= 10^51 <= prizePositions[i] <= 10^90 <= k <= 10^9prizePositions is sorted in non-decreasing order.
Hints for Maximize Win From Two Segments
Hint 1
First solve it for one segment: for each right-most prize, the segment ending there holds every prize within distance
k— a sliding window.Hint 2
With two segments, look for an optimal pair that does not overlap: one ends before the other starts (overlapping segments never beat shifting one of them apart).
Hint 3
Keep
best[i]= the most prizes one segment can collect among the firstiprizes. When the window[left, right]ends at prizeright, combine it withbest[left].
How to solve Maximize Win From Two Segments
A sliding window gives, for every right end, the best single segment ending there. Pairing it with the best segment that lies entirely to its left (a prefix maximum) covers every useful pair of segments.
Approach
- Keep
left = 0, an answerans = 0and an arraybestof lengthn + 1withbest[0] = 0. - For each
right, advanceleftwhileprizePositions[right] - prizePositions[left] > k; the window holdscur = right - left + 1prizes. - Update
ans = max(ans, cur + best[left])— the second segment uses only prizes before indexleft. - Set
best[right + 1] = max(best[right], cur). - Return
ans.
Why it works
Given any two segments, we can shrink the left one so it covers only prizes before the right one's first prize without losing anything collected (a prize in both counts once and is kept by the right one). So some optimum consists of a window [left, right] and a disjoint segment among prizes 0 .. left - 1, whose best value is exactly best[left]. The sliding window enumerates every maximal window by its right end.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Compare differences (
pos[right] - pos[left] > k) rather than computingpos[left] + k, which can overflow 32 bits. - Duplicated positions are separate prizes — count indices, not distinct positions.
- When all prizes fit in one segment, the second contributes 0 and the answer is
n.
Reference solution
Python
from typing import List
def maximizeWin(prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
best = [0] * (n + 1)
ans = 0
left = 0
for right in range(n):
while prizePositions[right] - prizePositions[left] > k:
left += 1
cur = right - left + 1
ans = max(ans, cur + best[left])
best[right + 1] = max(best[right], cur)
return ansJava
public static int maximizeWin(int[] prizePositions, int k) {
int n = prizePositions.length;
int[] best = new int[n + 1];
int ans = 0, left = 0;
for (int right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) left++;
int cur = right - left + 1;
ans = Math.max(ans, cur + best[left]);
best[right + 1] = Math.max(best[right], cur);
}
return ans;
}C++
int maximizeWin(vector<int>& prizePositions, int k) {
int n = prizePositions.size();
vector<int> best(n + 1, 0);
int ans = 0, left = 0;
for (int right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) left++;
int cur = right - left + 1;
ans = max(ans, cur + best[left]);
best[right + 1] = max(best[right], cur);
}
return ans;
}JavaScript
var maximizeWin = function(prizePositions, k) {
var n = prizePositions.length;
var best = new Array(n + 1).fill(0);
var ans = 0, left = 0;
for (var right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) left++;
var cur = right - left + 1;
if (cur + best[left] > ans) ans = cur + best[left];
best[right + 1] = Math.max(best[right], cur);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search