Problem Description

You are given an array start containing integers and an integer d. These represent n intervals where each interval i is defined as [start[i], start[i] + d].

Your task is to choose exactly n integers, where:

• The i-th integer must be chosen from the i-th interval [start[i], start[i] + d]
• Each interval contributes exactly one integer to your selection

The score of your chosen integers is defined as the minimum absolute difference between any two integers in your selection. In other words, if you choose integers a₁, a₂, ..., aₙ, the score is the smallest value of |aᵢ - aⱼ| for all pairs where i ≠ j.

Your goal is to maximize this score by strategically selecting one integer from each interval.

Example to illustrate:

• If start = [1, 4] and d = 2
• The intervals are [1, 3] and [4, 6]
• You need to pick one integer from [1, 3] and one from [4, 6]
• If you pick 3 from the first interval and 4 from the second, the score is |3 - 4| = 1
• If you pick 1 from the first interval and 6 from the second, the score is |1 - 6| = 5
• The maximum possible score would be 5

The problem asks you to return the maximum possible score that can be achieved.

Intuition

The key insight is that to maximize the minimum difference between chosen integers, we want to spread them out as much as possible. Think of it like placing n points on a number line where each point must fall within its designated interval - we want these points to be as evenly spaced as possible.

Since we're maximizing the minimum difference, we should consider what happens when we fix a minimum difference value. If we can successfully place all integers with at least distance x between consecutive ones, then we know x is achievable. If x is achievable, then any smaller value x' < x is also achievable (we can always place integers closer together if needed).

This monotonic property suggests binary search: we can search for the largest minimum difference that's still achievable.

Another crucial observation is that sorting the intervals by their start positions helps us make greedy choices. Once sorted, we can process intervals from left to right, and for each interval, we want to place our integer as far left as possible while maintaining the minimum distance from the previous integer. This greedy approach works because:

1. Placing an integer further left gives more room for subsequent integers
2. We must respect each interval's boundaries [start[i], start[i] + d]

The strategy becomes:

• Sort intervals by start position
• Binary search on the answer (minimum difference)
• For each candidate difference, greedily check if we can place all integers from left to right
• When checking, always place each integer at the earliest valid position: either at the interval's start or at last_position + minimum_difference, whichever is larger

This way, we transform the optimization problem into a series of decision problems ("Can we achieve minimum difference of at least x?"), which we can efficiently solve using binary search combined with a greedy validation algorithm.

Learn more about Greedy, Binary Search and Sorting patterns.

Solution Approach

The solution implements a binary search combined with a greedy validation function.

Step 1: Sorting First, we sort the start array in ascending order. This allows us to process intervals from left to right and make greedy decisions about where to place each integer.

Step 2: Binary Search Setup We set up binary search boundaries:

• Left boundary: l = 0 (minimum possible difference)
• Right boundary: r = start[-1] + d - start[0] (maximum possible difference between the rightmost point of the last interval and the leftmost point of the first interval)

Step 3: Binary Search Implementation We use binary search to find the largest minimum difference that satisfies our constraints:

while l < r:
    mid = (l + r + 1) >> 1  # equivalent to (l + r + 1) // 2
    if check(mid):
        l = mid  # mid is achievable, try larger values
    else:
        r = mid - 1  # mid is not achievable, try smaller values

Step 4: Validation Function check(mi) The core logic lies in the check function that determines if a minimum difference mi is achievable:

def check(mi: int) -> bool:
    last = -inf  # Track the position of the last placed integer
    for st in start:
        if last + mi > st + d:
            return False  # Cannot place an integer in this interval
        last = max(st, last + mi)  # Place integer at the earliest valid position
    return True

The validation works as follows:

• Initialize last = -inf to represent that no integer has been placed yet
• For each interval [st, st + d]:
  • Check if we can place an integer at least mi distance from the previous one
  • If last + mi > st + d, it means even placing at the rightmost position st + d wouldn't maintain the minimum distance, so return False
  • Otherwise, place the integer at max(st, last + mi):
    • If last + mi ≤ st, place at the interval's start st
    • If last + mi > st, place at last + mi (the earliest position maintaining the minimum distance)
• If all intervals can accommodate an integer with the required spacing, return True

Time Complexity: O(n log(max_range)) where n is the number of intervals and max_range is the difference between the maximum and minimum possible positions.

Space Complexity: O(1) if we don't count the sorting space, otherwise O(n) for sorting.

Example Walkthrough

Let's walk through a concrete example with start = [2, 6, 13, 13] and d = 5.

Step 1: Understanding the intervals

• Interval 0: [2, 7] (from 2 to 2+5)
• Interval 1: [6, 11] (from 6 to 6+5)
• Interval 2: [13, 18] (from 13 to 13+5)
• Interval 3: [13, 18] (from 13 to 13+5)

Step 2: Sort the intervals After sorting by start positions: [2, 6, 13, 13] (already sorted)

Step 3: Set up binary search

• Left boundary: l = 0
• Right boundary: r = 13 + 5 - 2 = 16

Step 4: Binary search iterations

Iteration 1:

• mid = (0 + 16 + 1) // 2 = 8
• Check if minimum difference of 8 is achievable:
  • Place in interval [2, 7]: last = -∞, so place at max(2, -∞ + 8) = 2. Update last = 2
  • Place in interval [6, 11]: need at least 2 + 8 = 10, place at max(6, 10) = 10. Update last = 10
  • Place in interval [13, 18]: need at least 10 + 8 = 18, place at max(13, 18) = 18. Update last = 18
  • Place in interval [13, 18]: need at least 18 + 8 = 26, but interval ends at 18. Cannot place!
• Result: check(8) = False, so r = 7

Iteration 2:

• mid = (0 + 7 + 1) // 2 = 4
• Check if minimum difference of 4 is achievable:
  • Place in interval [2, 7]: place at max(2, -∞ + 4) = 2. Update last = 2
  • Place in interval [6, 11]: place at max(6, 2 + 4) = 6. Update last = 6
  • Place in interval [13, 18]: place at max(13, 6 + 4) = 13. Update last = 13
  • Place in interval [13, 18]: place at max(13, 13 + 4) = 17. Update last = 17
• Result: check(4) = True, so l = 4

Iteration 3:

• mid = (4 + 7 + 1) // 2 = 6
• Check if minimum difference of 6 is achievable:
  • Place in interval [2, 7]: place at 2. Update last = 2
  • Place in interval [6, 11]: place at max(6, 2 + 6) = 8. Update last = 8
  • Place in interval [13, 18]: place at max(13, 8 + 6) = 14. Update last = 14
  • Place in interval [13, 18]: need at least 14 + 6 = 20, but interval ends at 18. Cannot place!
• Result: check(6) = False, so r = 5

Iteration 4:

• mid = (4 + 5 + 1) // 2 = 5
• Check if minimum difference of 5 is achievable:
  • Place in interval [2, 7]: place at 2. Update last = 2
  • Place in interval [6, 11]: place at max(6, 2 + 5) = 7. Update last = 7
  • Place in interval [13, 18]: place at max(13, 7 + 5) = 13. Update last = 13
  • Place in interval [13, 18]: place at max(13, 13 + 5) = 18. Update last = 18
• Result: check(5) = True, so l = 5

Iteration 5:

• Now l = 5 and r = 5, so the loop terminates.

Final Answer: 5

The optimal selection is: [2, 7, 13, 18]

• Difference between 2 and 7: |2 - 7| = 5
• Difference between 7 and 13: |7 - 13| = 6
• Difference between 13 and 18: |13 - 18| = 5
• Difference between 2 and 13: |2 - 13| = 11
• Difference between 2 and 18: |2 - 18| = 16
• Difference between 7 and 18: |7 - 18| = 11

The minimum difference among all pairs is 5, which matches our answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M), where n is the length of the start array and M represents the maximum possible score range, which is start[-1] + d - start[0] after sorting.

• Sorting the start array takes O(n log n) time.
• The binary search performs O(log M) iterations, where M = start[-1] + d - start[0] is the search range.
• In each binary search iteration, the check function is called, which iterates through all n elements in the sorted start array, taking O(n) time.
• Therefore, the binary search contributes O(n × log M) to the time complexity.
• Since O(n × log M) typically dominates O(n log n) for large values of M, the overall time complexity is O(n × log M).

Space Complexity: O(1) if we don't count the space used for sorting (in-place sorting), or O(log n) if we consider the recursive stack space used by the sorting algorithm.

• The algorithm uses only a constant amount of extra space for variables like l, r, mid, and last in the check function.
• The sorting operation may use O(log n) space for the recursive call stack in typical implementations like Timsort (Python's default).
• Following the reference answer's convention, the space complexity is considered O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Boundary Calculation

Pitfall: Using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when updating left = mid.

This leads to an infinite loop when left = right - 1. For example:

• If left = 3 and right = 4
• Using mid = (3 + 4) // 2 = 3
• If the check passes, we set left = mid = 3
• The loop continues infinitely since left doesn't change

Solution: Always use mid = (left + right + 1) // 2 (or (left + right + 1) >> 1) when the update pattern is left = mid and right = mid - 1.

2. Not Sorting the Intervals Before Processing

Pitfall: Forgetting to sort the start array before applying the greedy algorithm in the validation function.

Without sorting, the greedy approach fails because we can't guarantee that placing integers from left to right will give us an optimal solution. Consider:

• start = [10, 1], d = 2
• Without sorting, we'd try to place at interval [10, 12] first, then [1, 3]
• This makes validation unnecessarily complex and potentially incorrect

Solution: Always sort the intervals first: sorted_start = sorted(start)

3. Off-by-One Error in Binary Search Loop Condition

Pitfall: Using while left <= right instead of while left < right.

With left <= right, when left == right, the loop continues unnecessarily, and the final assignment could be incorrect depending on the last check result.

Solution: Use while left < right for this binary search pattern where we're looking for the maximum valid value.

4. Incorrect Greedy Placement in Validation

Pitfall: Placing integers at arbitrary positions within intervals instead of following the greedy principle of placing at the earliest valid position.

For example, placing at last_position + min_distance without checking if it exceeds the interval start:

# Wrong approach
last_position = last_position + min_distance

This fails when the calculated position is before the interval start.

Solution: Use last_position = max(start_pos, last_position + min_distance) to ensure we place at the earliest valid position within the interval.

5. Integer Overflow in Large Inputs

Pitfall: Not considering potential overflow when calculating positions or differences, especially with large values of start[i] and d.

Solution: In Python, this is generally not an issue due to arbitrary precision integers, but in other languages, use appropriate data types (e.g., long long in C++) or check for overflow conditions.