Scale Engineer

Maximize Win From Two Segments

Med
#2335Time: O(N^3), where N is the number of prizes. The three nested loops iterate through all pairs of starting positions and then all prizes.Space: O(N) in this implementation due to the HashSet. It can be O(1) if we calculate counts without a set.
Patterns
Sliding Window
Algorithms
Binary Search
Data structures
Array

Prompt

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:

[3, 3]

 

Constraints:

  • 1 <= prizePositions.length <= 105
  • 1 <= prizePositions[i] <= 109
  • 0 <= k <= 109
  • prizePositions is sorted in non-decreasing order.

 

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach is to try every possible pair of segments. Since the optimal segments will have their endpoints aligned with prize positions to maximize coverage, we can assume each segment starts at some prizePositions[i]. We can iterate through all pairs of starting indices (i, j) for the two segments. For each pair, we calculate the total number of unique prizes covered by the union of the two segments and keep track of the maximum number found.

Algorithm

  1. Initialize maxPrizes to 0.
  2. Iterate through each possible starting position i for the first segment, from 0 to n-1.
  3. Inside this loop, iterate through each possible starting position j for the second segment, from i to n-1.
  4. For each pair (i, j), define the two segments:
    • S1 = [prizePositions[i], prizePositions[i] + k]
    • S2 = [prizePositions[j], prizePositions[j] + k]
  5. Count the number of prizes in the union of S1 and S2. A simple way to do this is to iterate through all prizes from p = 0 to n-1 and check if prizePositions[p] falls into S1 or S2. A HashSet can be used to store the indices of the prizes collected to avoid double counting.
  6. Update maxPrizes with the maximum count found.
  7. Return maxPrizes.

Walkthrough

This method exhaustively checks every combination of two segments. The start of each segment is chosen from one of the prize positions. For each pair of segments, we determine the total number of unique prizes they cover.

To implement this, we can use nested loops. The outer loop selects the starting prize for the first segment, and the inner loop selects the starting prize for the second segment. For each pair of segments, we can iterate through all the prizes and count how many fall within at least one of the two segments. To handle overlaps correctly (i.e., not counting a prize twice if it's in both segments), we can use a HashSet to store the indices of the prizes collected.

import java.util.HashSet; class Solution {    public int maximizeWin(int[] prizePositions, int k) {        int n = prizePositions.length;        if (n == 0) {            return 0;        }        int maxPrizes = 0;         // If only one segment is used        if (n > 0) {            for (int i = 0; i < n; i++) {                int rightBound = prizePositions[i] + k;                int count = 0;                for (int p = i; p < n; p++) {                    if (prizePositions[p] <= rightBound) {                        count++;                    } else {                        break;                    }                }                maxPrizes = Math.max(maxPrizes, count);            }        }         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                long start1 = prizePositions[i];                long end1 = start1 + k;                long start2 = prizePositions[j];                long end2 = start2 + k;                 HashSet<Integer> collectedPrizes = new HashSet<>();                for (int p = 0; p < n; p++) {                    if ((prizePositions[p] >= start1 && prizePositions[p] <= end1) ||                         (prizePositions[p] >= start2 && prizePositions[p] <= end2)) {                        collectedPrizes.add(p);                    }                }                maxPrizes = Math.max(maxPrizes, collectedPrizes.size());            }        }        return maxPrizes;    }}

This version has a time complexity of O(N^3). A slightly better O(N^2 log N) approach would involve calculating the counts for each segment and their intersection using binary search instead of the innermost loop, but it's still too slow for the given constraints.

Complexity

Time

O(N^3), where N is the number of prizes. The three nested loops iterate through all pairs of starting positions and then all prizes.

Space

O(N) in this implementation due to the HashSet. It can be O(1) if we calculate counts without a set.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • The time complexity is very high, making it unsuitable for the given constraints.

Solutions

class Solution {public  int maximizeWin(int[] prizePositions, int k) {    int n = prizePositions.length;    int[] f = new int[n + 1];    int ans = 0;    for (int i = 1; i <= n; ++i) {      int x = prizePositions[i - 1];      int j = search(prizePositions, x - k);      ans = Math.max(ans, f[j] + i - j);      f[i] = Math.max(f[i - 1], i - j);    }    return ans;  }private  int search(int[] nums, int x) {    int left = 0, right = nums.length;    while (left < right) {      int mid = (left + right) >> 1;      if (nums[mid] >= x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem