2555. Maximize Win From Two Segments
Problem Description
In this problem, you're presented with a number line where various prizes are located at different positions, represented by the sorted integer array prizePositions
. Your goal is to collect as many of those prizes as possible by selecting two segments on the number line. Each segment is defined by integer endpoints and has a fixed length k
. Any prize positioned within these segments or on their boundaries is considered collected.
The key complication is that there are constraints on the size of the segments; both must be exactly k
units long, which means you have to be strategic about where you place them. Two segments may even overlap, allowing for potential strategies where you might cover a dense cluster of prizes with the intersection of both segments. The task is to determine the maximum number of prizes you can win by choosing the two segments with optimal positions.
Intuition
The intuition behind the solution is to utilize a sliding window approach where we iterate over the prizes, keeping track of the number of prizes that can be collected with a segment ending at the current prize's position. We can do this efficiently because the prizePositions
array is sorted.
As we iterate through the prizes, we use binary search, implemented in Python as bisect_left
, to find the leftmost position in the prizePositions
array where we can start a segment of length k
that ends at the current prize's position (x
). This allows us to calculate how many prizes we can collect for every possible ending position of a segment.
Since we're allowed to have two segments, we need to determine the best way to combine two such segments to maximize the number of prizes. While iterating, we maintain an array f
that keeps track of the best solution for the first segment ending at each position. As we compute the maximum prizes for a segment ending at position x
, we also consider the best solution (f[j]
) for the segment that would end right before the start of the current segment.
By updating ans
with f[j] + i - j
, we continuously keep track of the best combination of two segments up to the current prize's position. i - j
represents the number of prizes we collect from the current segment, and f[j]
the most prizes collected from the first segment that does not overlap with the current one. f[i]
is then updated to be the maximum of the previous value or i - j
, ensuring f
remains accurate as we progress.
Learn more about Binary Search and Sliding Window patterns.
Solution Approach
The solution follows a dynamic programming strategy with the aid of binary search to efficiently handle the sorted nature of the prizePositions
. Here's a walkthrough explaining the role of different parts of the code:
-
Initialization:
n
is assigned to be the length of theprizePositions
list and signifies the total number of prizes.f
is then initialized to be a list of zeros with a length one more than the number of prizes (n + 1
), wheref[i]
will store the maximum number of prizes that can be obtained by the first segment ending atprizePositions[i - 1]
. The extra entry allows handling the case where no prizes fit into the first segment.ans
is initialized to 0, which will ultimately hold the maximum number of prizes obtained with two segments.
-
Iterating over prizes:
- The
for
loop iterates throughprizePositions
withx
representing the position of the current prize andi
the index (1-based). - Using
bisect_left(prizePositions, x - k)
, we perform a binary search to find the indexj
where a segment of lengthk
could start such that it will end exactly at the current prize positionx
. Since our list is 1-based in this scope,j
actually represents the number of prizes that are unreachable by the segment ending atx
.
- The
-
Calculating the maximum number of prizes:
ans
is updated to check if the current combination of the first segment ending right beforej
and the second segment ending atx
yields a higher prize count than previously recorded. Here,f[j]
gives the number of prizes for the optimal first segment andi - j
represents the number of prizes collected by a segment ending atx
starting from positionj
.f[i]
is then updated to hold the maximum number of prizes that can be collected with this current segment as the potential first segment for future iterations:f[i] = max(f[i - 1], i - j)
.
The algorithm utilizes dynamic programming to remember previous results and applies binary search to make it efficient for finding start points of segments within the sorted prize positions. The choice of f
being a list of n + 1
integers and the use of binary search is crucial for keeping the overall time complexity low as it avoids any need for nested loops, and each lookup or operation is done in constant to logarithmic time, leading to an overall time complexity of O(n log n).
The final result, ans
, gives us the maximum number of prizes selectable with two optimally placed segments of length k
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate this solution approach with a small example. Suppose we're given the sorted integer array prizePositions
and a segment length k
.
prizePositions = [1, 3, 4, 8, 10] k = 4
-
Initialization:
- The list has 5 positions, so
n = 5
. - We have
f = [0, 0, 0, 0, 0, 0]
to capture the maximum prizes for any first segment ending at each prize index. ans
starts with a value of 0.
- The list has 5 positions, so
-
Iterating over prizes:
- We start the loop, for each
x
inprizePositions
,i
is the index starting at 1. - At
i = 1
,x = 1
: We can't fit any segment that ends at1
and is 4 units long because the segment would start before the number line. - At
i = 2
,x = 3
: A segment of length 4 can start at positionprizePositions[0]
, so it collects 2 prizes ([1, 3]
).
- We start the loop, for each
-
Calculating the maximum number of prizes:
- For
i = 2
, using binary search,j = bisect_left(prizePositions, 3 - 4)
, which givesj = 0
since no segment of length 4 can end before 3. - Since this is the first viable segment,
ans
is updated to bef[j] + (i - j)
, which is0 + (2 - 0) = 2
. - Update
f[i]
to bemax(f[i - 1], i - j)
, sof[2]
becomesmax(f[1], 2 - 0)
which is2
.
- For
Continuing this process:
- At
i = 3
,x = 4
: A segment of length 4 can start at positionprizePositions[0]
, collecting 3 prizes ([1, 3, 4]
) withj = 0
. Nowans
is updated to3
. f[3]
becomes3
asmax(f[2], 3 - 0)
.- At
i = 4
,x = 8
: A segment of length 4 can start atprizePositions[1] = 3
, collecting 2 prizes ([3, 4]
) withj = 1
. Nowans
compares2 (f[1]) + 2
with3
and keeps3
. f[4]
takes the higher off[3]
or3 - 1
, so it becomes3
.- At
i = 5
,x = 10
: A segment of length 4 can start atprizePositions[2] = 4
, collecting 3 prizes ([4, 8, 10]
) withj = 2
. Hereans
compares3 (f[2]) + 3
with currentans
and updates it to6
. - Finally,
f[5]
becomesmax(f[4], 5 - 2)
which is3
.
At the end of the process, ans
gives us 6
, which is the maximum number of prizes we can collect by optimally placing two segments of length k
(each collecting [1, 3, 4]
and [4, 8, 10]
, with overlap on the prize at position 4
).
The solution efficiently finds the maximum number of prizes using sliding windows and binary search within the constraints given, leading to an optimal pairing of segments with potentially overlapping positions.
Solution Implementation
1from bisect import bisect_left
2
3class Solution:
4 def maximizeWin(self, prize_positions: List[int], k: int) -> int:
5 # Get the number of available positions
6 num_positions = len(prize_positions)
7 # Initialize the dp (dynamic programming) array with zeroes
8 dp = [0] * (num_positions + 1)
9 # 'max_win' will store the maximum number of wins attainable
10 max_win = 0
11
12 # Iterate through the prize positions
13 for i, position in enumerate(prize_positions, 1):
14 # Find the leftmost position in 'prize_positions' where the player could have been
15 # to ensure the distance between consecutive prizes is at most 'k'
16 j = bisect_left(prize_positions, position - k)
17
18 # The current win is calculated by previous win at 'j' plus the number of positions
19 # between 'j' and the current position 'i', update 'max_win' accordingly
20 max_win = max(max_win, dp[j] + i - j)
21
22 # Update the dp array with the maximum of the previous value or the new calculated win
23 dp[i] = max(dp[i - 1], i - j)
24
25 # Finally, return the maximum number of wins after processing all positions
26 return max_win
27
1class Solution {
2
3 // Method to maximize the win given a set of prize positions and a distance k.
4 public int maximizeWin(int[] prizePositions, int k) {
5 int n = prizePositions.length; // Total number of prizes.
6 int[] dp = new int[n + 1]; // Dynamic programming array.
7 int maxPrizes = 0; // Variable to keep track of the maximum number of prizes.
8
9 // Loop through each prize position.
10 for (int i = 1; i <= n; ++i) {
11 int currentPosition = prizePositions[i - 1]; // Current position under consideration.
12 int j = binarySearch(prizePositions, currentPosition - k); // Finding the eligible position.
13 // Update the maximum number of prizes.
14 maxPrizes = Math.max(maxPrizes, dp[j] + i - j);
15 // Update the DP array with the maximum prizes up to the current index.
16 dp[i] = Math.max(dp[i - 1], i - j);
17 }
18 return maxPrizes; // Return the maximum number of prizes that can be won.
19 }
20
21 // Binary search to find the index of the smallest number greater than or equal to x.
22 private int binarySearch(int[] nums, int x) {
23 int left = 0, right = nums.length;
24
25 // Perform the binary search.
26 while (left < right) {
27 int mid = (left + right) >> 1; // Find the middle index.
28 // Check if the middle element is greater than or equal to x.
29 if (nums[mid] >= x) {
30 right = mid; // Adjust the right boundary.
31 } else {
32 left = mid + 1; // Adjust the left boundary.
33 }
34 }
35 // Return the index of the left boundary, which gives the desired position.
36 return left;
37 }
38}
39
1#include <vector>
2#include <algorithm> // for std::lower_bound and std::max
3
4class Solution {
5public:
6 // Function to find the maximum number of prizes that can be won in a game,
7 // given the prize positions and the maximum distance k a player can move.
8 int maximizeWin(std::vector<int>& prizePositions, int k) {
9 int n = prizePositions.size(); // Get the number of prize positions
10 std::vector<int> memo(n + 1); // Create a DP array for memoization, initialized to n+1 elements
11 int maxPrizes = 0; // This will hold the maximum number of prizes that can be won
12
13 // Iterate over each prize position
14 for (int i = 1; i <= n; ++i) {
15 int currentPosition = prizePositions[i - 1]; // Get the current prize position
16
17 // Find the first position that is within the distance k from currentPosition
18 auto it = lower_bound(prizePositions.begin(), prizePositions.end(), currentPosition - k);
19 int j = it - prizePositions.begin(); // Find the index of the position
20
21 // Update maxPrizes to be the larger value between its current value and the prizes won if starting from j
22 maxPrizes = std::max(maxPrizes, memo[j] + i - j);
23
24 // Update the DP table with the maximum of the current value or the i - j prizes
25 memo[i] = std::max(memo[i - 1], i - j);
26 }
27
28 return maxPrizes; // Return the maximum number of prizes that can be won
29 }
30};
31
1// Maximizes the number of prizes won by jumping exactly k positions to the right each time
2function maximizeWin(prizePositions: number[], k: number): number {
3 const prizeCount = prizePositions.length;
4 // Array to hold the maximum number of prizes that can be won up to a certain position
5 const maxPrizes: number[] = Array(prizeCount + 1).fill(0);
6 let maxWin = 0;
7
8 // Searches for the leftmost position where the player can jump from to reach the current position or beyond
9 const binarySearch = (targetPosition: number): number => {
10 let left = 0;
11 let right = prizeCount;
12 while (left < right) {
13 const mid = (left + right) >> 1;
14 if (prizePositions[mid] >= targetPosition) {
15 right = mid;
16 } else {
17 left = mid + 1;
18 }
19 }
20 return left;
21 };
22
23 // Iterate through all prize positions to calculate the maximum number of prizes that can be won
24 for (let i = 1; i <= prizeCount; ++i) {
25 const currentPosition = prizePositions[i - 1];
26 const jumpFromIndex = binarySearch(currentPosition - k);
27 maxWin = Math.max(maxWin, maxPrizes[jumpFromIndex] + i - jumpFromIndex);
28 maxPrizes[i] = Math.max(maxPrizes[i - 1], i - jumpFromIndex);
29 }
30
31 return maxWin;
32}
33
Time and Space Complexity
The given Python code aims to determine the maximum number of prizes one can win within a window or gap of 'k
' positions.
Time Complexity:
The function maximizeWin
iterates once over the prizePositions
list, which contains 'n
' elements. For every element 'x
' in 'prizePositions', there is a call to bisect_left
, which performs binary search on the sorted list of prize positions, having a time complexity of O(log n)
.
The loop runs for 'n
' times, so considering both the loop and the binary search inside it, the overall time complexity is O(n log n)
, where 'n
' is the number of elements in the prizePositions
list.
Space Complexity:
Space complexity is determined by the extra space used in addition to the input data size. The algorithm allocates a list 'f
' with 'n + 1
' elements, where 'n
' is the length of prizePositions
.
Thus, the space complexity of the code is O(n)
, which is required for the auxiliary list 'f
'. Since this list scales linearly with the input size, the usage of constant extra variables is negligible compared to the size of 'f
'.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!