Domain 2MediumMEDIUM

Magnetic Force Between Two Balls

Maximize the minimum distance between m balls in n baskets by sorting positions and using binary search on the answer with a greedy feasibility check.

Domain: medium•Updated: 2026-09-18
#Binary Search#Greedy#$O(N log N + K)$#$O(1)

Problem Breakdown

We are given n baskets located at specific integer coordinates (position) and need to place exactly m balls into these baskets. The goal is to maximize the minimum magnetic force (distance) between any two adjacent placed balls.

  • Inputs: An array of basket positions (position, unsorted initially) and an integer count of balls (m).
  • Output: The maximum possible value for the minimum distance achieved.
  • Constraints & Properties:
    • Basket locations are distinct integers (no duplicates).
    • Positions can be up to 10910^9, requiring binary search on values rather than iteration over coordinates.
    • m is always less than or equal to the number of baskets (n).
  • Key Insight: The problem exhibits monotonicity: if a minimum distance d is achievable, any distance smaller than d is also achievable. This allows Binary Search on the Answer space (distance values).

Intuition

A brute-force approach checking every combination of m baskets out of n results in exponential complexity (nm)\binom{n}{m}, which is impossible for N=105N=10^5.

Instead, we observe that if it’s possible to place balls with a minimum force of at least X, then any value less than X is also feasible. This monotonic property suggests Binary Search on the Answer. We search through the range of possible forces (from 1 up to max coordinate difference). For each candidate distance (mid), we check feasibility using a greedy strategy: place balls as far apart as allowed while maintaining at least mid separation. If feasible, try larger distances; otherwise, reduce the target force.

Approach

  1. Sort Positions: Sort the position array in ascending order (O(Nlog⁡N)O(N \log N)). This is crucial to process baskets linearly and calculate adjacent distances correctly for greedy placement.
  2. Binary Search Setup:
    • Define search range: low = 1, high = position[-1] - position[0]. The maximum possible force cannot exceed the total span of coordinates. Since positions are distinct integers, minimum valid distance is at least 1.
  3. Feasibility Check (canPlace): Inside the binary loop:
    • Place the first ball at position[0] (leftmost basket) to maximize remaining space for subsequent balls. This greedy choice works because placing a ball earlier never hurts feasibility compared to later placement if distances are constrained by minimum separation.
    • Iterate through sorted baskets starting from index 1. If current distance ≥\ge mid, place the next ball and update last position.
    • Count placed balls. Return True if count reaches m. Include an early break optimization when all m balls are placed to save time in feasible cases.
  4. Binary Search Logic:
    • If feasible (count >= m): Store current mid as potential answer, try higher forces (low = mid + 1).
    • If not feasible: Try lower forces (high = mid - 1).

Complexity Analysis

  • Time Complexity: O(Nlog⁡N+K⋅N)O(N \log N + K \cdot N), where NN is the number of baskets and KK is ≈log⁡(max_coordinate)\approx \log(\text{max\_coordinate}). Sorting takes O(Nlog⁡N)O(N \log N). The binary search runs for K=O(log⁡(109))≤32K = O(\log(10^9)) \le 32 iterations. Each iteration scans the array in O(N)O(N). Thus, total time is dominated by sorting and linear passes: roughly O(N(log⁡N+K))O(N (\log N + K)).
  • Space Complexity: O(1)O(1) auxiliary space (ignoring input storage). Python’s sort() uses Timsort which may use temporary memory proportional to the number of runs but generally considered efficient; strictly speaking, it modifies in-place or requires minimal extra stack.

Solution

from typing import List

def maxDistance(position: List[int], m: int) -> int:
    # Sort positions to enable linear greedy check for feasibility
    position.sort()
    
    n = len(position)
    low, high = 1, position[-1] - position[0]
    ans = 0
    
    while low <= high:
        mid = (low + high) // 2
        
        # Greedy check: Can we place m balls with at least 'mid' distance?
        count = 1  # Place first ball in the first basket always
        last_pos = position[0]
        
        for i in range(1, n):
            if position[i] - last_pos >= mid:
                count += 1
                last_pos = position[i]
                
                # Optimization: If we already placed all balls, break early
                if count == m:
                    break
        
        if count < m:
            high = mid - 1
        else:
            ans = mid
            low = mid + 1
            
    return ans

# Example usage for verification (not part of submission)
if __name__ == "__main__":
    print(maxDistance([1,2,3,4,7], 3)) # Output: 3
    print(maxDistance([5,4,3,2,1,1000000000], 2)) # Output: 999999999

Edge Cases Handled

  • Unsorted Input: The solution explicitly sorts position at the start. Without this, distance calculations between non-adjacent indices in a sorted list would be incorrect for greedy placement logic.
  • Large Coordinates (10910^9): Binary search operates on values rather than iterating through coordinates, preventing Time Limit Exceeded (TLE) errors associated with O(max_val)O(\text{max\_val}).
  • Minimum Balls (m=2): The loop correctly handles the case where only two balls are needed. Since we always place the first ball at index 0 and iterate to find count >= m, it effectively checks max distance between endpoints when feasible.
  • All Baskets Used: If n=mn = m, the logic naturally places a ball in every basket, resulting in minimum force being min⁡(position[i+1]−position[i])\min(position[i+1] - position[i]). The binary search will converge on this value correctly as count reaches m.