Maximize Win From Two Segments - Practice Coding Problems

Maximize Win From Two Segments - 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 the maximum number of prizes you can win if you choose the two segments optimally.

Input & Output

Example 1 — Basic Case

$ Input: prizePositions = [1,1,2,2,3,3,5], k = 2

› Output: 6

💡 Note: Choose segments [1,3] and [3,5]. Segment [1,3] covers prizes at positions 1,1,2,2,3,3 (6 prizes total). Segment [3,5] covers prizes at positions 3,3,5 (3 prizes). Union covers 6 unique prizes.

Example 2 — Non-overlapping Optimal

$ Input: prizePositions = [1,2,3,4], k = 1

› Output: 4

💡 Note: Choose segments [1,2] and [3,4]. First segment covers positions 1,2 (2 prizes), second segment covers positions 3,4 (2 prizes). Total: 4 prizes.

Example 3 — Single Position Multiple Prizes

$ Input: prizePositions = [1,1,1,1], k = 0

› Output: 4

💡 Note: Both segments can cover position [1,1], capturing all 4 prizes at position 1.

Constraints

1 ≤ prizePositions.length ≤ 10⁵
1 ≤ prizePositions[i] ≤ 10⁹
0 ≤ k ≤ 10⁹
prizePositions is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Prize positions [1,1,2,2,3,3,5] with segment length k=2

Process

Find optimal placement of two segments of length k

Output

Maximum 6 prizes can be captured

Key Takeaway

🎯 Key Insight: Pre-compute optimal segments and use efficient boundary detection to maximize prize coverage

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to optimize segment selection by precomputing maximum obtainable prizes from each position and using efficient boundary detection. Best approach uses sliding window with precomputation for O(n²) time complexity, or binary search optimization for O(n log n). Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Precomputation	O(n²)	O(n)	Use sliding window to efficiently count prizes in each segment
Brute Force - Try All Segment Pairs	O(n³)	O(1)	Try every possible pair of segments and count total prizes
Two-Pass with Binary Search	O(n log n)	O(n)	Use binary search for efficient segment boundary finding

Sliding Window with Precomputation — Algorithm Steps

Pre-compute suffix maximums for optimal second segment placement
For each first segment position, use sliding window to count prizes
Find best non-overlapping second segment using precomputed values
Handle overlapping segments separately

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Calculate max prizes for each possible segment start

Sliding Window

Use window to efficiently count prizes in first segment

Optimal Second

Use precomputed values to find best second segment

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* prizePositions, int n, int k) {
    if (n == 0) return 0;
    
    // Precompute maximum prizes for segments starting at each position
    int* maxFromPos = (int*)malloc(n * sizeof(int));
    int j = 0;
    
    for (int i = 0; i < n; i++) {
        int start = prizePositions[i];
        int end = start + k;
        
        // Count prizes in this segment
        while (j < n && prizePositions[j] <= end) {
            j++;
        }
        
        maxFromPos[i] = j - i;
    }
    
    // Compute suffix maximum
    int* suffixMax = (int*)calloc(n + 1, sizeof(int));
    for (int i = n - 1; i >= 0; i--) {
        suffixMax[i] = max(suffixMax[i + 1], maxFromPos[i]);
    }
    
    int maxPrizes = 0;
    j = 0;
    
    // Try each position as first segment start
    for (int i = 0; i < n; i++) {
        int start1 = prizePositions[i];
        int end1 = start1 + k;
        
        // Count prizes in first segment
        while (j < n && prizePositions[j] <= end1) {
            j++;
        }
        
        int firstSegmentPrizes = j - i;
        
        // Find first position after current segment
        int nextPos = j;
        while (nextPos < n && prizePositions[nextPos] <= end1) {
            nextPos++;
        }
        
        // Best second segment from remaining positions
        int secondSegmentPrizes = nextPos < n ? suffixMax[nextPos] : 0;
        
        maxPrizes = max(maxPrizes, firstSegmentPrizes + secondSegmentPrizes);
    }
    
    free(maxFromPos);
    free(suffixMax);
    return maxPrizes;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int prizePositions[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            prizePositions[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(prizePositions, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop for first segment positions (O(n)) and inner sliding window operations (O(n) total)

⚠ Quadratic Growth

Space Complexity

O(n)

Arrays for precomputed suffix maximums and segment counts

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Precomputation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler