LeetCode 3281 - Maximize Score of Numbers in Ranges

The problem presents a list of intervals derived from the start array and a fixed d. Specifically, each interval is [start[i], start[i] + d].

leetcodemediumarraybinary-searchgreedysorting

LeetCode Problem 3281

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem presents a list of intervals derived from the start array and a fixed d. Specifically, each interval is [start[i], start[i] + d]. The goal is to select exactly one integer from each interval such that the minimum absolute difference between any two chosen integers is maximized. In other words, you want to spread the chosen numbers as far apart as possible, while staying within their respective intervals.

The input start represents the starting points of intervals and d is the fixed interval length. The output is a single integer representing the largest possible minimum difference among chosen numbers.

Constraints indicate that start can be very large (up to 10^5) and the numbers themselves can be very large (up to 10^9). This rules out any brute-force approach that considers all possible integer selections, because the search space is exponential. Edge cases include intervals of length zero (where d = 0) or multiple identical intervals (which can reduce the maximum possible score).

Approaches

A brute-force approach would try every combination of integers from each interval and compute the minimum absolute difference for each combination. While this would guarantee correctness, it is clearly infeasible because there are potentially (d+1)^n combinations, which is enormous given n can reach 10^5.

The key insight for an optimal solution is to realize that the problem can be treated as a maximum minimum distance problem, commonly solved using a binary search on the answer. Specifically, you can binary search on the possible minimum difference score and, for each candidate value, attempt to greedily assign numbers from left to right to satisfy that minimum distance. Sorting intervals by their start point ensures that this greedy approach will always try the earliest possible number in each interval, leaving maximum room for subsequent numbers.

Approach Time Complexity Space Complexity Notes
Brute Force O((d+1)^n) O(n) Try every combination of integer selections from intervals.
Optimal O(n log(range)) O(n) Binary search on minimum difference + greedy placement. range is the numeric span of the intervals.

Algorithm Walkthrough

  1. Sort the intervals based on the start values. This ensures we can process intervals from left to right.

  2. Define the search range for binary search. The minimum possible score is 0 and the maximum possible score is max(start) + d - min(start), the full range spanned by all intervals.

  3. Binary search on score (the candidate minimum absolute difference):

  4. Initialize low = 0 and high = max_range.

  5. While low <= high, compute mid = (low + high) // 2 as the candidate score.

  6. Greedy placement check: Start with the first interval, choose the smallest number in that interval, and for each subsequent interval, choose the earliest number that is at least mid away from the previous number. If this is impossible for any interval, the candidate mid is too high.

  7. If placement succeeds, move low = mid + 1 (we can try a higher score); otherwise, move high = mid - 1.

  8. Return high as the largest score that passed the greedy check.

Why it works: Sorting ensures that the greedy choice of the earliest valid number is optimal because it leaves maximum room for future intervals. Binary search guarantees that the largest feasible minimum difference is found efficiently.

Python Solution

from typing import List

class Solution:
    def maxPossibleScore(self, start: List[int], d: int) -> int:
        intervals = sorted((s, s + d) for s in start)
        
        def can_achieve(score: int) -> bool:
            prev = intervals[0][0]
            for l, r in intervals[1:]:
                candidate = max(prev + score, l)
                if candidate > r:
                    return False
                prev = candidate
            return True
        
        low, high = 0, max(r for _, r in intervals) - min(l for l, _ in intervals)
        result = 0
        while low <= high:
            mid = (low + high) // 2
            if can_achieve(mid):
                result = mid
                low = mid + 1
            else:
                high = mid - 1
        return result

The code first converts start into intervals and sorts them. The helper can_achieve checks whether a given minimum score is feasible by greedily choosing numbers. Binary search then efficiently finds the maximum feasible score.

Go Solution

func maxPossibleScore(start []int, d int) int {
    n := len(start)
    intervals := make([][2]int, n)
    for i, s := range start {
        intervals[i] = [2]int{s, s + d}
    }
    
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    
    canAchieve := func(score int) bool {
        prev := intervals[0][0]
        for i := 1; i < n; i++ {
            candidate := max(prev + score, intervals[i][0])
            if candidate > intervals[i][1] {
                return false
            }
            prev = candidate
        }
        return true
    }
    
    low, high := 0, intervals[n-1][1] - intervals[0][0]
    result := 0
    for low <= high {
        mid := (low + high) / 2
        if canAchieve(mid) {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

In Go, the approach is identical. Arrays are used for intervals, and sort.Slice handles sorting. canAchieve performs greedy placement, and binary search finds the maximum feasible score.

Worked Examples

Example 1: start = [6,0,3], d = 2

Intervals: [6,8], [0,2], [3,5] sorted → [0,2], [3,5], [6,8].

Binary search checks candidate score = 4:

  • Pick 0 from [0,2]
  • Next interval [3,5], earliest ≥ 0 + 4 → candidate 4 → fits in [3,5] → pick 4
  • Next interval [6,8], earliest ≥ 4 + 4 → candidate 8 → fits in [6,8] → pick 8

Minimum difference among chosen = 4, feasible.

Example 2: start = [2,6,13,13], d = 5

Intervals: [2,7], [6,11], [13,18], [13,18]

Candidate score = 5:

  • Pick 2 from [2,7]
  • Next [6,11], earliest ≥ 2 + 5 → 7 → pick 7
  • Next [13,18], earliest ≥ 7 + 5 → 12 → fits [13,18]? Pick 13 (≥12)
  • Next [13,18], earliest ≥ 13 + 5 → 18 → fits [13,18]? Pick 18

Minimum difference = 5, feasible.

Complexity Analysis

Measure Complexity Explanation
Time O(n log R) n intervals, binary search on range R = max(start) + d - min(start) and greedy check O(n) each.
Space O(n) Storing intervals and temporary variables.

The binary search over the numeric range is efficient because the interval range can be up to 10^9, so log(R) ≈ 30, which is negligible compared to n ≤ 10^5.

Test Cases

# Provided examples
assert Solution().maxPossibleScore([6,0,3], 2) == 4  # Example 1
assert Solution().maxPossibleScore([2,6,13,13], 5) == 5  # Example 2

# Edge cases
assert Solution().maxPossibleScore([0,0], 0) == 0  # intervals of length 0
assert Solution().maxPossibleScore([0,1,2], 0) == 1  # minimal spread
assert Solution().maxPossibleScore([0,1000000000], 0) == 1000000000  # max span

# Larger input
assert Solution().maxPossibleScore([i*10 for i in range(1000)], 5) == 10  # uniform spacing
Test Why
[6,0,3], 2 Basic example, small numbers
[2,6,13,13], 5 Multiple intervals with overlap
[0,0], 0 Interval length 0
[0,1,2], 0 Minimal spacing
[0,10^9],0 Max range edge case
`[i*10 for i in range(1000)],5