Problem

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 themaximum number of prizes you can win if you choose the two segments optimally.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^5
  • 1 <= prizePositions[i] <= 10^9
  • 0 <= k <= 10^9
  • prizePositions is sorted in non-decreasing order.

Solution

Method 1 – Sliding Window + Prefix Maximum

Intuition

Since the array is sorted, we can use a sliding window to find the maximum number of prizes that can be collected in a segment of length k ending at each position. To maximize the total, we can combine two such segments, possibly overlapping, by keeping track of the best result for the left segment as we move the right segment.

Approach

  1. Use two pointers (l and r) to maintain a window where all prizes are within k of prizePositions[r].
  2. For each r, calculate the number of prizes in the current window.
  3. Maintain a prefix maximum array where pre[r] is the best segment ending at or before r.
  4. For each r, the answer is the sum of the current window and the best left segment that ends before the current window starts.
  5. Return the maximum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        vector<int> pre(n+1, 0);
        int ans = 0, l = 0;
        for (int r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            int cnt = r - l + 1;
            pre[r+1] = max(pre[r], cnt);
        }
        l = 0;
        for (int r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            int cnt = r - l + 1;
            ans = max(ans, cnt + pre[l]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func maximizeWin(prizePositions []int, k int) int {
    n := len(prizePositions)
    pre := make([]int, n+1)
    ans, l := 0, 0
    for r := 0; r < n; r++ {
        for prizePositions[r]-prizePositions[l] > k {
            l++
        }
        cnt := r - l + 1
        if pre[r] > cnt {
            pre[r+1] = pre[r]
        } else {
            pre[r+1] = cnt
        }
    }
    l = 0
    for r := 0; r < n; r++ {
        for prizePositions[r]-prizePositions[l] > k {
            l++
        }
        cnt := r - l + 1
        if ans < cnt+pre[l] {
            ans = cnt + pre[l]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        int[] pre = new int[n+1];
        int ans = 0, l = 0;
        for (int r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            int cnt = r - l + 1;
            pre[r+1] = Math.max(pre[r], cnt);
        }
        l = 0;
        for (int r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            int cnt = r - l + 1;
            ans = Math.max(ans, cnt + pre[l]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maximizeWin(prizePositions: IntArray, k: Int): Int {
        val n = prizePositions.size
        val pre = IntArray(n+1)
        var ans = 0
        var l = 0
        for (r in 0 until n) {
            while (prizePositions[r] - prizePositions[l] > k) l++
            val cnt = r - l + 1
            pre[r+1] = maxOf(pre[r], cnt)
        }
        l = 0
        for (r in 0 until n) {
            while (prizePositions[r] - prizePositions[l] > k) l++
            val cnt = r - l + 1
            ans = maxOf(ans, cnt + pre[l])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def maximizeWin(self, prizePositions: list[int], k: int) -> int:
        n = len(prizePositions)
        pre = [0] * (n+1)
        ans = l = 0
        for r in range(n):
            while prizePositions[r] - prizePositions[l] > k:
                l += 1
            cnt = r - l + 1
            pre[r+1] = max(pre[r], cnt)
        l = 0
        for r in range(n):
            while prizePositions[r] - prizePositions[l] > k:
                l += 1
            cnt = r - l + 1
            ans = max(ans, cnt + pre[l])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn maximize_win(prize_positions: Vec<i32>, k: i32) -> i32 {
        let n = prize_positions.len();
        let mut pre = vec![0; n+1];
        let mut ans = 0;
        let mut l = 0;
        for r in 0..n {
            while prize_positions[r] - prize_positions[l] > k {
                l += 1;
            }
            let cnt = r - l + 1;
            pre[r+1] = pre[r].max(cnt);
        }
        l = 0;
        for r in 0..n {
            while prize_positions[r] - prize_positions[l] > k {
                l += 1;
            }
            let cnt = r - l + 1;
            ans = ans.max(cnt + pre[l]);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximizeWin(prizePositions: number[], k: number): number {
        const n = prizePositions.length;
        const pre = new Array(n+1).fill(0);
        let ans = 0, l = 0;
        for (let r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            const cnt = r - l + 1;
            pre[r+1] = Math.max(pre[r], cnt);
        }
        l = 0;
        for (let r = 0; r < n; ++r) {
            while (prizePositions[r] - prizePositions[l] > k) ++l;
            const cnt = r - l + 1;
            ans = Math.max(ans, cnt + pre[l]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each pointer only moves forward through the array.
  • 🧺 Space complexity: O(n), for the prefix maximum array.