Skip to main content
Talentd

Maximize Win From Two Segments - Solution & Explanation

MediumArrayBinary SearchSliding Window12 min readAsked at: Uber
Practice this problem

Problem Statement

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 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 get 2 prizes.

 

Constraints:

  • 1 <= prizePositions.length <= 105
  • 1 <= prizePositions[i] <= 109
  • 0 <= k <= 109
  • prizePositions is 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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), as we iterate through the list using two pointers.
Space Complexity: O(n), due to the 'currentSegment' array.

Try this approach in the editor →

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.

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.

Code

C++Java

C++

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Technique

Time Complexity: O(n), as we iterate through the list using two pointers.
Space Complexity: O(n), due to the 'currentSegment' array.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window TechniqueO(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 SearchO(n log n)O(n)Useful when computing ranges independently with binary search before combining segments

Video Solution

Maximize Win From Two Segments | Biweekly Contest 97 | Leetcode • codingMohan • 2,575 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximize Win From Two Segments with our built-in code editor and test cases.

Practice on FleetCode
Previous

Best Time to Buy and Sell Stock III

Next

Two Best Non-Overlapping Events