LeetCode 1552 - Magnetic Force Between Two Balls

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

Solution

Problem Understanding

The problem asks us to distribute m balls into n baskets located at given positions along a line in such a way that the minimum distance between any two balls is maximized. The magnetic force between two balls is defined as the absolute difference of their positions. In simpler terms, we want to place the balls so that the closest pair of balls is as far apart as possible.

The input consists of an array position of integers representing the baskets' coordinates and an integer m representing the number of balls. The output is a single integer, the largest possible value for the minimum distance between any two balls when optimally distributed.

Constraints tell us that n can be up to 10^5 and the positions can be as large as 10^9. The positions are distinct, and m is at least 2. These constraints indicate that an algorithm with time complexity worse than O(n log n) will likely be too slow, and careful handling of large integers is necessary.

Important edge cases include situations where the baskets are widely spaced, the balls are fewer than baskets, or the balls must be placed at extreme ends of the array to maximize distance.

Approaches

Brute Force Approach

A naive approach would be to try all combinations of placing m balls into n baskets, compute the minimum distance for each configuration, and return the largest minimum distance found. This guarantees correctness because we exhaustively check all possibilities, but it is computationally infeasible for large n and m since the number of combinations is combinatorial: O(C(n, m)), which grows rapidly with input size.

Optimal Approach

The key insight is to use binary search on the answer. Instead of checking every placement, we can determine whether a certain minimum distance d is feasible: if we can place all m balls such that each is at least d units apart. If a distance is feasible, larger distances may also be feasible, otherwise smaller distances are needed.

Sorting the position array allows us to greedily place balls: start at the first basket and place each subsequent ball at the first basket that is at least d away from the last placed ball. If we can place all m balls using this method, the distance d is feasible.

We then perform binary search over the possible range of distances from 1 to the maximum difference between the smallest and largest basket positions.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n, m) * m)	O(1)	Exhaustively checks all placements, infeasible for n up to 10^5
Optimal	O(n log(max_pos - min_pos))	O(1)	Uses sorting and binary search with a greedy feasibility check

Algorithm Walkthrough

Sort the position array. Sorting allows us to check feasible placements in a single left-to-right pass.
Define the search range for binary search. low is 1 (smallest possible minimum distance), high is the distance between the first and last basket (position[-1] - position[0]).
Perform binary search:
Compute the middle distance mid = (low + high) // 2.
Check if it is possible to place m balls with at least mid distance between them:
Place the first ball at the first basket.
Iterate through the positions, placing a ball whenever the distance from the last placed ball is at least mid.
Count the total balls placed.
If we can place all m balls, mid is feasible. Set low = mid + 1 to try larger distances.
Otherwise, set high = mid - 1 to try smaller distances.
When binary search finishes, high contains the largest feasible minimum distance.

Why it works: The greedy placement ensures that if a distance d is feasible, any smaller distance is also feasible. Binary search efficiently finds the maximum feasible d by exploiting the monotonicity of feasibility.

Python Solution

from typing import List

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def can_place(distance: int) -> bool:
            count = 1
            last_position = position[0]
            for pos in position[1:]:
                if pos - last_position >= distance:
                    count += 1
                    last_position = pos
                    if count == m:
                        return True
            return False
        
        low, high = 1, position[-1] - position[0]
        result = 0
        while low <= high:
            mid = (low + high) // 2
            if can_place(mid):
                result = mid
                low = mid + 1
            else:
                high = mid - 1
        return result

The Python implementation first sorts the positions to allow greedy placement. The can_place helper function counts how many balls can be placed given a minimum distance. Binary search iteratively refines the feasible distance and returns the largest one.

Go Solution

import "sort"

func maxDistance(position []int, m int) int {
    sort.Ints(position)
    
    canPlace := func(distance int) bool {
        count := 1
        last := position[0]
        for _, pos := range position[1:] {
            if pos - last >= distance {
                count++
                last = pos
                if count == m {
                    return true
                }
            }
        }
        return false
    }
    
    low, high := 1, position[len(position)-1] - position[0]
    result := 0
    for low <= high {
        mid := (low + high) / 2
        if canPlace(mid) {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

The Go version mirrors the Python logic. Sorting is done using sort.Ints. The closure canPlace checks feasibility. Integer division is used for binary search midpoint. Go slices naturally handle iteration, avoiding index errors.

Worked Examples

Example 1: position = [1,2,3,4,7], m = 3

After sorting: [1,2,3,4,7].

Binary search range: low = 1, high = 6.

Iteration	mid	can_place(mid)	low	high	result
1	3	True	4	6	3
2	5	False	4	4	3
3	4	False	4	3	3

Output: 3.

Example 2: position = [5,4,3,2,1,1000000000], m = 2

After sorting: [1,2,3,4,5,1000000000].

Binary search quickly finds that placing balls at positions 1 and 1000000000 maximizes distance: 999999999.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log(max_pos - min_pos))	Sorting takes O(n log n), binary search does O(log(max_pos - min_pos)) iterations, each checking O(n) positions.
Space	O(1)	Only variables for binary search and counting are used; sorting may use O(n) in-place depending on implementation.

The algorithm is efficient for n up to 10^5 and positions up to 10^9.

Test Cases

# Provided examples
assert Solution().maxDistance([1,2,3,4,7], 3) == 3  # Example 1
assert Solution().maxDistance([5,4,3,2,1,1000000000], 2) == 999999999  # Example 2

# Edge cases
assert Solution().maxDistance([1,100], 2) == 99  # Small input
assert Solution().maxDistance([1,2,3,4,5], 5) == 1  # Balls equal to baskets
assert Solution().maxDistance([1,3,6,10,15], 3) == 7  # Spread balls in middle
assert Solution().maxDistance([1,2,4,8,16,32], 3) == 15  # Exponential spacing
assert Solution().maxDistance([1,2], 2) == 1  # Minimum input

Test	Why
[1,2,3,4,7], 3	Example from problem statement
[5,4,3,2,1,1000000000], 2	Large distance case
[1,100], 2	Minimum number of baskets with max spacing
[1,2,3,4,5], 5	Number of balls equals number of baskets
[1,3,6,10,15], 3	Regular spacing, test greedy placement
[1,2,4,8,16