Solution Approach

The solution implements binary search using the standard template combined with a greedy verification function.

1. Sort the positions array: First, we sort the basket positions to enable the greedy placement strategy.

2. Define the feasible function: We define feasible(d) as "we CANNOT place m balls with minimum distance d". This creates a pattern:

[false, false, ..., false, true, true, ..., true]

We want to find the first distance where placement becomes impossible.

3. Greedy verification: To check if we can place m balls with distance d:

• Place the first ball at position[0]
• Greedily place each subsequent ball at the first position that is at least d away from the previous ball
• Count how many balls we can place
• Return count < m (true if we cannot place all m balls)

4. Binary search using the template:

left, right = 1, position[-1] - position[0]
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if not can_place_balls(mid):  # feasible: cannot place m balls
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

5. Calculate the answer: The answer is first_true_index - 1 (the largest distance where we CAN place all balls). If first_true_index == -1, all distances in range work, so return the maximum distance.

Time Complexity: O(n log n + n log M) where n is the number of baskets and M is the position range.

Space Complexity: O(log n) for sorting.

Example Walkthrough

Let's walk through a concrete example with baskets at positions [1, 2, 3, 4, 7] and we need to place m = 3 balls.

Step 1: Sort positions The array is already sorted: [1, 2, 3, 4, 7]

Step 2: Understand the feasible function feasible(d) = "cannot place 3 balls with minimum distance d"

• d=1: can place at 1,2,3 → false (can place)
• d=2: can place at 1,3,7 → false (can place)
• d=3: can place at 1,4,7 → false (can place)
• d=4: can only place at 1,7 (2 balls) → true (cannot place 3)
• d=5: can only place at 1,7 (2 balls) → true (cannot place 3)
• d=6: can only place at 1,7 (2 balls) → true (cannot place 3)

Pattern: [false, false, false, true, true, true] → first_true_index = 4

Step 3: Binary search using template Initialize: left = 1, right = 6, first_true_index = -1

Iteration 1: left=1, right=6

• mid = (1 + 6) // 2 = 3
• Can place 3 balls with distance 3? Place at 1, then 4, then 7 → Yes!
• can_place_balls(3) = true, so feasible(3) = false
• left = mid + 1 = 4

Iteration 2: left=4, right=6

• mid = (4 + 6) // 2 = 5
• Can place 3 balls with distance 5? Place at 1, then need 6+, only 7 works → Only 2 balls
• can_place_balls(5) = false, so feasible(5) = true
• first_true_index = 5, right = mid - 1 = 4

Iteration 3: left=4, right=4

• mid = (4 + 4) // 2 = 4
• Can place 3 balls with distance 4? Place at 1, then need 5+, only 7 works → Only 2 balls
• can_place_balls(4) = false, so feasible(4) = true
• first_true_index = 4, right = mid - 1 = 3

Loop ends as left > right (4 > 3).

Step 4: Calculate the answer

• first_true_index = 4 (first distance where we cannot place 3 balls)
• Answer = first_true_index - 1 = 3 (last distance where we can place 3 balls)

Final Answer: 3

The optimal placement is at positions 1, 4, and 7, giving minimum distance 3.

Time and Space Complexity

Time Complexity: O(n × log n + n × log M)

The time complexity consists of two main parts:

• O(n × log n) for sorting the position array, where n is the length of the position array
• O(n × log M) for the binary search operation, where:
  • The binary search runs O(log M) iterations, with M = position[-1] - 1 being the search range (from 1 to the maximum position value)
  • Each iteration calls the check function, which iterates through all n positions in O(n) time
  • Combined: O(n × log M)

Space Complexity: O(log n)

The space complexity comes from:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursion stack
• The check function uses O(1) additional space with only a few variables (prev, cnt, curr)
• The binary search itself uses O(1) space for variables l and r
• The dominant factor is the sorting's recursion stack: O(log n)

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

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with left = mid (finding last true) instead of the standard template with first_true_index.

Wrong variant:

while left < right:
    mid = (left + right + 1) // 2  # Ceiling to avoid infinite loop
    if can_place_balls(mid):
        left = mid
    else:
        right = mid - 1
return left

Correct template:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if not can_place_balls(mid):  # Invert: true when cannot place
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index - 1 if first_true_index != -1 else right

2. Incorrect Binary Search Bounds

Setting right bound as position[-1] (a position) instead of position[-1] - position[0] (maximum distance).

Wrong:

right = position[-1]  # This is a position, not a distance

Correct:

right = position[-1] - position[0]  # Maximum possible distance

3. Off-by-One Error in Result Calculation

When using first_true_index (first distance where placement fails), the answer is first_true_index - 1.

Wrong:

return first_true_index  # Returns first invalid distance!

Correct:

return first_true_index - 1  # Last valid distance

4. Not Handling first_true_index == -1

If all distances allow placement, first_true_index stays -1. Must handle this case.

Solution:

if first_true_index == -1:
    return position[-1] - position[0]  # All distances work
return first_true_index - 1

5. Greedy Placement Starting Position

Always place the first ball at position[0]. Don't use -inf which complicates logic.

Simpler approach:

def can_place_balls(min_distance):
    balls_placed = 1  # First ball at position[0]
    prev = position[0]

    for i in range(1, len(position)):
        if position[i] - prev >= min_distance:
            balls_placed += 1
            prev = position[i]

    return balls_placed >= m

Template-Compliant Solution:

def maxDistance(self, position: List[int], m: int) -> int:
    def can_place_balls(min_distance: int) -> bool:
        balls_placed = 1
        prev = position[0]
        for i in range(1, len(position)):
            if position[i] - prev >= min_distance:
                balls_placed += 1
                prev = position[i]
        return balls_placed >= m

    position.sort()
    left, right = 1, position[-1] - position[0]
    first_true_index = -1

    while left <= right:
        mid = (left + right) // 2
        if not can_place_balls(mid):
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    if first_true_index == -1:
        return position[-1] - position[0]
    return first_true_index - 1