We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Win From Two Segments

Number: 2673

Difficulty: Medium

Paid? No

Companies: Uber

Problem Description

Given a sorted array prizePositions representing positions on the X-axis where prizes are located (there may be duplicates), and an integer k, you may select two segments of length k (with integer endpoints). Each segment covers prizes with positions between its endpoints (inclusive). The two segments can overlap. The goal is to maximize the total number of prizes captured by the two segments.

Key Insights

  • Because prizePositions is sorted, a two-pointer (sliding window) approach can efficiently calculate how many prizes fall inside a segment covering [x, x+k].
  • Precompute for each index the number of prizes that can be captured starting at that position by moving the right pointer until the prize position exceeds prizePositions[i] + k.
  • Build an auxiliary suffix array to keep track of the maximum count for segments starting at or after any given index.
  • For each segment represented by a starting index, combine its count with the best count from a segment starting after its interval ends.
  • Binary Search can also be used to find the ending index of each segment, but the sliding window method is direct and efficient.

Space and Time Complexity

Time Complexity: O(n) – two pointers traverse the prizePositions array linearly and the suffix array is built in O(n).
Space Complexity: O(n) – extra arrays are used to store counts for each window and the suffix maximum counts.

Solution

We first use a sliding window to compute the number of prizes that can be captured by a segment starting at each prizePositions[i] (i.e. covering [prizePositions[i], prizePositions[i]+k]). This gives us a count array. As we determine the window for prizePositions[i], we also compute the index where the window ends.
Next, we build a suffix array such that for any index i, suf[i] represents the maximum count of any segment starting from index i to the end of prizePositions.
Finally, for each starting segment, we combine its count with the best possible count from a segment that does not interfere (i.e. where the left endpoint is outside the current segment’s range). The final answer is the maximum sum found among all such pairs, ensuring we consider cases where one segment might cover all the prizes.

Code Solutions

# Python solution for "Maximize Win From Two Segments"
# Using sliding window and suffix max approach
def maximizeWin(prizePositions, k):
    n = len(prizePositions)
    count = [0] * n  # count[i] stores number of prizes in window starting at i
    right = 0

    # Calculate prizes counts for each window starting at index i using two pointers
    for left in range(n):
        # Move right pointer to the right as long as prizePositions[right] is within prizePositions[left] + k
        while right < n and prizePositions[right] <= prizePositions[left] + k:
            right += 1
        count[left] = right - left  # prizes in the segment [prizePositions[left], prizePositions[left]+k]

    # Build suffix maximum array where suf[i] is the maximum count for windows starting from index i onwards
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = max(count[i], suf[i + 1])

    ans = 0
    j = 0  # j pointer for the next window outside current segment [prizePositions[i], prizePositions[i]+k]
    for i in range(n):
        # Move pointer j so that prizePositions[j] > prizePositions[i] + k
        # This ensures that the second segment does not overlap the first segment's starting window
        while j < n and prizePositions[j] <= prizePositions[i] + k:
            j += 1
        # Combine current window count with the best possible window starting at index j or later
        # suf[j] is 0 if j >= n.
        total = count[i] + (suf[j] if j < n else 0)
        ans = max(ans, total)

    return ans

# Example Usage:
print(maximizeWin([1,1,2,2,3,3,5], 2))  # Output: 7
print(maximizeWin([1,2,3,4], 0))          # Output: 2
← Back to All Questions