2555. Maximize Win From Two Segments

MediumArrayBinary SearchSliding Window
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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:

  1. Initialization:

    • n is assigned to be the length of the prizePositions 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), where f[i] will store the maximum number of prizes that can be obtained by the first segment ending at prizePositions[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.

  2. Iterating over prizes:

    • The for loop iterates through prizePositions with x representing the position of the current prize and i the index (1-based).
    • Using bisect_left(prizePositions, x - k), we perform a binary search to find the index j where a segment of length k could start such that it will end exactly at the current prize position x. Since our list is 1-based in this scope, j actually represents the number of prizes that are unreachable by the segment ending at x.

  3. Calculating the maximum number of prizes:

    • ans is updated to check if the current combination of the first segment ending right before j and the second segment ending at x yields a higher prize count than previously recorded. Here, f[j] gives the number of prizes for the optimal first segment and i - j represents the number of prizes collected by a segment ending at x starting from position j.
    • 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example 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.

1prizePositions = [1, 3, 4, 8, 10]
2k = 4

  1. 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.

  2. Iterating over prizes:

    • We start the loop, for each x in prizePositions, i is the index starting at 1.
    • At i = 1, x = 1: We can't fit any segment that ends at 1 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 position prizePositions[0], so it collects 2 prizes ([1, 3]).

  3. Calculating the maximum number of prizes:

    • For i = 2, using binary search, j = bisect_left(prizePositions, 3 - 4), which gives j = 0 since no segment of length 4 can end before 3.
    • Since this is the first viable segment, ans is updated to be f[j] + (i - j), which is 0 + (2 - 0) = 2.
    • Update f[i] to be max(f[i - 1], i - j), so f[2] becomes max(f[1], 2 - 0) which is 2.

Continuing this process:

  • At i = 3, x = 4: A segment of length 4 can start at position prizePositions[0], collecting 3 prizes ([1, 3, 4]) with j = 0. Now ans is updated to 3.
  • f[3] becomes 3 as max(f[2], 3 - 0).
  • At i = 4, x = 8: A segment of length 4 can start at prizePositions[1] = 3, collecting 2 prizes ([3, 4]) with j = 1. Now ans compares 2 (f[1]) + 2 with 3 and keeps 3.
  • f[4] takes the higher of f[3] or 3 - 1, so it becomes 3.
  • At i = 5, x = 10: A segment of length 4 can start at prizePositions[2] = 4, collecting 3 prizes ([4, 8, 10]) with j = 2. Here ans compares 3 (f[2]) + 3 with current ans and updates it to 6.
  • Finally, f[5] becomes max(f[4], 5 - 2) which is 3.

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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Binary Search Speedrun

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

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫