Maximize Win From Two Segments

Medium
1364.

Maximize Win From Two Segments

Maximize Win From Two Segments is a medium coding problem on arrays, binary search and sliding window, asked in Amazon and Google interviews.

Prizes lie on the number line. prizePositions lists their positions in non-decreasing order; several prizes may share a position.

You may choose two segments with integer endpoints, each of length exactly k — a segment [l, l + k] collects every prize whose position lies within it, ends included. The segments may overlap, and a prize inside both is still collected once.

Return the maximum number of prizes you can collect.

Example 1

Input
prizePositions = [1,2,2,4,7,8,8,12], k = 2
Output
6
Explanation
`[1,3]` collects 1, 2, 2 and `[7,9]` collects 7, 8, 8.

Example 2

Input
prizePositions = [3,3,3], k = 0
Output
3
Explanation
The single point segment `[3,3]` already holds all three prizes.

Example 3

Input
prizePositions = [1,5,9,13], k = 1
Output
2
Explanation
Each segment can reach only one prize.

Constraints

  • 1 <= prizePositions.length <= 10^5
  • 1 <= prizePositions[i] <= 10^9
  • 0 <= k <= 10^9
  • prizePositions is sorted in non-decreasing order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prizePositions
 * @param {number} k
 * @return {number}
 */
var maximizeWin = function(prizePositions, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Win From Two Segments — Problem & Solution

Maximize Win From Two Segments solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximize Win From Two Segments is a medium coding problem on arrays, binary search and sliding window, asked in Amazon and Google interviews.

Problem statement

Prizes lie on the number line. prizePositions lists their positions in non-decreasing order; several prizes may share a position.

You may choose two segments with integer endpoints, each of length exactly k — a segment [l, l + k] collects every prize whose position lies within it, ends included. The segments may overlap, and a prize inside both is still collected once.

Return the maximum number of prizes you can collect.

Example 1

Input: prizePositions = [1,2,2,4,7,8,8,12], k = 2
Output: 6
Explanation: `[1,3]` collects 1, 2, 2 and `[7,9]` collects 7, 8, 8.

Example 2

Input: prizePositions = [3,3,3], k = 0
Output: 3
Explanation: The single point segment `[3,3]` already holds all three prizes.

Example 3

Input: prizePositions = [1,5,9,13], k = 1
Output: 2
Explanation: Each segment can reach only one prize.

Constraints

  • 1 <= prizePositions.length <= 10^5
  • 1 <= prizePositions[i] <= 10^9
  • 0 <= k <= 10^9
  • prizePositions is sorted in non-decreasing order.

Hints for Maximize Win From Two Segments

  1. Hint 1

    First solve it for one segment: for each right-most prize, the segment ending there holds every prize within distance k — a sliding window.

  2. Hint 2

    With two segments, look for an optimal pair that does not overlap: one ends before the other starts (overlapping segments never beat shifting one of them apart).

  3. Hint 3

    Keep best[i] = the most prizes one segment can collect among the first i prizes. When the window [left, right] ends at prize right, combine it with best[left].

How to solve Maximize Win From Two Segments

A sliding window gives, for every right end, the best single segment ending there. Pairing it with the best segment that lies entirely to its left (a prefix maximum) covers every useful pair of segments.

Approach

  1. Keep left = 0, an answer ans = 0 and an array best of length n + 1 with best[0] = 0.
  2. For each right, advance left while prizePositions[right] - prizePositions[left] > k; the window holds cur = right - left + 1 prizes.
  3. Update ans = max(ans, cur + best[left]) — the second segment uses only prizes before index left.
  4. Set best[right + 1] = max(best[right], cur).
  5. Return ans.

Why it works

Given any two segments, we can shrink the left one so it covers only prizes before the right one's first prize without losing anything collected (a prize in both counts once and is kept by the right one). So some optimum consists of a window [left, right] and a disjoint segment among prizes 0 .. left - 1, whose best value is exactly best[left]. The sliding window enumerates every maximal window by its right end.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Compare differences (pos[right] - pos[left] > k) rather than computing pos[left] + k, which can overflow 32 bits.
  • Duplicated positions are separate prizes — count indices, not distinct positions.
  • When all prizes fit in one segment, the second contributes 0 and the answer is n.

Reference solution

Python

from typing import List

def maximizeWin(prizePositions: List[int], k: int) -> int:
    n = len(prizePositions)
    best = [0] * (n + 1)
    ans = 0
    left = 0
    for right in range(n):
        while prizePositions[right] - prizePositions[left] > k:
            left += 1
        cur = right - left + 1
        ans = max(ans, cur + best[left])
        best[right + 1] = max(best[right], cur)
    return ans

Java

public static int maximizeWin(int[] prizePositions, int k) {
    int n = prizePositions.length;
    int[] best = new int[n + 1];
    int ans = 0, left = 0;
    for (int right = 0; right < n; right++) {
        while (prizePositions[right] - prizePositions[left] > k) left++;
        int cur = right - left + 1;
        ans = Math.max(ans, cur + best[left]);
        best[right + 1] = Math.max(best[right], cur);
    }
    return ans;
}

C++

int maximizeWin(vector<int>& prizePositions, int k) {
    int n = prizePositions.size();
    vector<int> best(n + 1, 0);
    int ans = 0, left = 0;
    for (int right = 0; right < n; right++) {
        while (prizePositions[right] - prizePositions[left] > k) left++;
        int cur = right - left + 1;
        ans = max(ans, cur + best[left]);
        best[right + 1] = max(best[right], cur);
    }
    return ans;
}

JavaScript

var maximizeWin = function(prizePositions, k) {
    var n = prizePositions.length;
    var best = new Array(n + 1).fill(0);
    var ans = 0, left = 0;
    for (var right = 0; right < n; right++) {
        while (prizePositions[right] - prizePositions[left] > k) left++;
        var cur = right - left + 1;
        if (cur + best[left] > ans) ans = cur + best[left];
        best[right + 1] = Math.max(best[right], cur);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search