2555. Maximize Win From Two Segments LeetCode Solution

In this guide, you will get 2555. Maximize Win From Two Segments LeetCode Solution with the best time and space complexity. The solution to Maximize Win From Two Segments problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximize Win From Two Segments solution in C++
Maximize Win From Two Segments solution in Java
Maximize Win From Two Segments solution in Python
Additional Resources

2555. Maximize Win From Two Segments LeetCode Solution image

Problem Statement of Maximize Win From Two Segments

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2555. Maximize Win From Two Segments LeetCode Solution in C++

class Solution {
 public:
  int maximizeWin(vector<int>& prizePositions, int k) {
    int ans = 0;
    // dp[i] := the maximum number of prizes to choose the first i
    // `prizePositions`
    vector<int> dp(prizePositions.size() + 1);

    for (int i = 0, j = 0; i < prizePositions.size(); ++i) {
      while (prizePositions[i] - prizePositions[j] > k)
        ++j;
      const int covered = i - j + 1;
      dp[i + 1] = max(dp[i], covered);
      ans = max(ans, dp[j] + covered);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2555. Maximize Win From Two Segments LeetCode Solution in Java

class Solution {
  public int maximizeWin(int[] prizePositions, int k) {
    int ans = 0;
    // dp[i] := the maximum number of prizes to choose the first i
    // `prizePositions`
    int[] dp = new int[prizePositions.length + 1];

    for (int i = 0, j = 0; i < prizePositions.length; ++i) {
      while (prizePositions[i] - prizePositions[j] > k)
        ++j;
      final int covered = i - j + 1;
      dp[i + 1] = Math.max(dp[i], covered);
      ans = Math.max(ans, dp[j] + covered);
    }

    return ans;
  }
}
// code provided by PROGIEZ

2555. Maximize Win From Two Segments LeetCode Solution in Python

class Solution:
  def maximizeWin(self, prizePositions: list[int], k: int) -> int:
    ans = 0
    # dp[i] := the maximum number of prizes to choose the first i
    # `prizePositions`
    dp = [0] * (len(prizePositions) + 1)

    j = 0
    for i, prizePosition in enumerate(prizePositions):
      while prizePosition - prizePositions[j] > k:
        j += 1
      covered = i - j + 1
      dp[i + 1] = max(dp[i], covered)
      ans = max(ans, dp[j] + covered)

    return ans
 # code by PROGIEZ