Skip to main content
Talentd

Maximize Score of Numbers in Ranges - Solution & Explanation

MediumArrayBinary SearchGreedySorting21 min readAsked at: Amazon, De Shaw
Practice this problem

Problem Statement

You are given an array of integers start and an integer d, representing n intervals [start[i], start[i] + d].

You are asked to choose n integers where the ith integer must belong to the ith interval. The score of the chosen integers is defined as the minimum absolute difference between any two integers that have been chosen.

Return the maximum possible score of the chosen integers.

 

Example 1:

Input: start = [6,0,3], d = 2

Output: 4

Explanation:

The maximum possible score can be obtained by choosing integers: 8, 0, and 4. The score of these chosen integers is min(|8 - 0|, |8 - 4|, |0 - 4|) which equals 4.

Example 2:

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

Output: 5

Explanation:

The maximum possible score can be obtained by choosing integers: 2, 7, 13, and 18. The score of these chosen integers is min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|) which equals 5.

 

Constraints:

  • 2 <= start.length <= 105
  • 0 <= start[i] <= 109
  • 0 <= d <= 109

Approach Overview

Problem Overview: You are given multiple numeric ranges. From each range, you must pick exactly one number. The goal is to maximize the minimum difference between any two chosen numbers after ordering them. This turns the task into spacing selections as far apart as possible while staying inside each interval.

Approach 1: Greedy Selection from Intervals (O(n log n) time, O(1) space)

Sort the ranges by their starting value using sorting. Then iterate through the intervals and always pick the smallest feasible number that keeps the difference from the previously chosen number as large as possible. The greedy rule is simple: choose max(range_start, prev + diff) while ensuring the value does not exceed the interval's end. This works because selecting the earliest valid number leaves the most room for later intervals. The approach relies on interval ordering and greedy placement to maintain spacing.

Approach 2: Binary Search for Optimal Difference (O(n log n + n log D) time, O(1) space)

The optimal solution uses binary search on the answer. Instead of directly maximizing the score, guess a candidate minimum difference d. Then verify if it's possible to pick numbers from each interval such that every chosen value is at least d apart. The feasibility check runs greedily: iterate through sorted intervals and place the earliest allowed value that is ≥ prev + d. If the value exceeds the interval end, the candidate difference is impossible. Because feasibility is monotonic (if d works, smaller values also work), binary search efficiently finds the largest valid difference.

The greedy feasibility check leverages the ordered structure of intervals and ensures each placement keeps future choices flexible. This pattern—binary searching the answer while validating with a greedy pass—is common in spacing problems involving arrays, greedy strategies, and interval constraints.

Recommended for interviews: The binary search on the answer combined with a greedy feasibility check is the approach most interviewers expect. It demonstrates understanding of monotonic properties and interval placement. Implementing the greedy check first helps validate the idea, while the binary search layer shows algorithmic optimization.

Approach 1: Greedy Selection from Intervals

This approach leverages a simple greedy strategy to select the number at the upper bound of each interval if possible. This choice maximizes the subsequent space for the next interval and hence the difference between the numbers chosen from consecutive intervals.

Sorting the intervals from smallest to largest ensures that we're optimizing space allocation sequentially.

The implementation sorts the array of start points and then iterates through the start points to determine the minimum difference required to keep all choices within the respective intervals. Since the intervals are sorted, any potential increasing pattern is accounted for by finding the difference across consecutive points adjusted for the interval spread.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) as we sort in place.

Try this approach in the editor →

Approach 2: Binary Search for Optimal Difference

This approach leverages binary search to identify the maximum score possible through repeatedly checking if a specific minimum difference is feasible. Adjusting the range and verifying selections ensures a balanced computational load while persistently searching for the exact maximum.

Binary search allows pruning of feasible solutions, narrowing results efficiently.

This method checks feasibility of a given minimum distance using a binary search pattern. By evaluating if selections remain within bounds and still approximate a candidate score, this optimizes towards the highest valid solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(maxDifference)) combining sorting and binary search iterations.
Space Complexity: O(1) - no additional storage apart from input modification.

Try this approach in the editor →

Approach 3: Sorting + Binary Search

We can first sort the start array. Then, we consider selecting integers from left to right, where the score is equal to the minimum difference between any two adjacent selected integers.

If a difference x satisfies the condition, then any x' < x will also satisfy the condition. Therefore, we can use binary search to find the largest difference that satisfies the condition.

We define the left boundary of the binary search as l = 0 and the right boundary as r = start[-1] + d - start[0]. Each time, we take the middle value mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor and check whether it satisfies the condition.

We define a function check(mi) to determine whether the condition is satisfied, implemented as follows:

  • We define a variable last = -infty, representing the last selected integer.
  • We traverse the start array. If last + mi > st + d, it means we cannot select the integer st, and we return false. Otherwise, we update last = max(st, last + mi).
  • If we traverse the entire start array and all conditions are satisfied, we return true.

The time complexity is O(n times log M), where n and M are the length and the maximum value of the start array, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Selection from Intervals

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) as we sort in place.

Binary Search for Optimal Difference

Time Complexity: O(n log(maxDifference)) combining sorting and binary search iterations.
Space Complexity: O(1) - no additional storage apart from input modification.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Selection from IntervalsO(n log n)O(1)When verifying feasibility of placements or building the greedy core logic for interval selection
Binary Search for Optimal DifferenceO(n log n + n log D)O(1)General case to maximize the minimum distance between chosen values across ranges

Video Solution

Maximize Score of Numbers in Ranges || LeetCode Weekly Contest 414 || Leetcode Solution • codi • 2,001 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize Score of Numbers in Ranges easy or hard?
The problem is generally classified as Medium. The greedy feasibility check is straightforward, but recognizing that the answer can be optimized with binary search requires experience with spacing and monotonic decision problems.
Maximize Score of Numbers in Ranges Python/Java solution
In Python or Java, the typical implementation sorts the intervals, performs binary search over the possible difference range, and runs a greedy check to place numbers. The greedy step tracks the last selected value and ensures the next chosen value is at least the candidate difference away.
How to solve Maximize Score of Numbers in Ranges in O(n)?
A pure O(n) solution is not typical because the intervals generally must be sorted first. After sorting, each feasibility check runs in O(n) using a greedy placement strategy. The complete optimal approach becomes O(n log n + n log D) due to sorting and binary search.
What is the best approach for Maximize Score of Numbers in Ranges?
The most efficient approach uses binary search on the minimum difference combined with a greedy feasibility check. After sorting the ranges, binary search guesses the minimum spacing and verifies whether numbers can be chosen from each interval while maintaining that distance. This reduces the problem to O(n log n + n log D) time.
Is Maximize Score of Numbers in Ranges asked at Google/Amazon/Meta?
Problems involving maximizing minimum distance with binary search and greedy placement frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include aggressive cows, placing routers, and interval spacing problems.
What data structure is used in Maximize Score of Numbers in Ranges?
The main structure is a sorted array of intervals. The algorithm relies on greedy iteration across the array while maintaining the previously selected value. Binary search is used to optimize the minimum allowed difference.
What is the time complexity of Maximize Score of Numbers in Ranges?
The optimal solution runs in O(n log n + n log D) time. Sorting the ranges takes O(n log n), and each binary search step performs a linear greedy check over the intervals. Space complexity is O(1) beyond the input array.

Ready to solve this problem?

Practice Maximize Score of Numbers in Ranges with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find K-th Smallest Pair Distance