#1552

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Magnetic Force Between Two Balls

Maximize the minimum magnetic force between balls by strategically placing them in baskets using binary search on positions.

array binary search sorting

Problem Statement

Rick has discovered a new form of magnetic force between balls in baskets across the universe. You are given n baskets at distinct integer positions, and Morty has m balls to distribute such that the minimum magnetic force between any two balls is as large as possible. The magnetic force between two balls at positions x and y is defined as |x - y|.

Given an integer array position representing basket locations and an integer m, determine the maximum possible minimum magnetic force achievable when placing all m balls into the baskets. You must select the optimal placement strategy to maximize this minimum distance.

Examples

Example 1

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

Output: 3

Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2

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

Output: 999999999

We can use baskets 1 and 1000000000.

Constraints

n == position.length
2 <= n <= 105
1 <= position[i] <= 109
All integers in position are distinct.
2 <= m <= position.length

Solution Approach

Sort positions and initialize search

Start by sorting the array of basket positions. Then, set the binary search range with left as 1 and right as the distance between the first and last basket. Sorting ensures that checking feasible placements is efficient.

Binary search over the answer space

Perform binary search over the potential minimum forces. For each mid value, attempt to greedily place balls starting from the first basket, ensuring each subsequent ball is at least mid distance apart. If placement succeeds for mid, move the search to higher distances; otherwise, reduce the range.

Greedy placement check

Iterate through sorted positions, placing the next ball only when the distance from the last placed ball is at least the candidate force. Count the balls placed, and if all m balls are successfully placed, the candidate force is feasible. This check is repeated for each mid in the binary search.

Complexity Analysis

Metric	Value
Time	O(n \log \frac{n * k}{m})
Space	O( \log n )

Sorting positions costs O(n log n). Binary search over the answer space has log(max distance) iterations, and each placement check iterates over n positions, giving overall time complexity O(n log(max_distance)) and space complexity O(log n) for recursion stack in sorting.

What Interviewers Usually Probe

Sorting positions before attempting placements is essential to make greedy checks feasible.
Binary search over distances rather than positions is a critical insight for this problem pattern.
Greedy placement confirms feasibility and drives the adjustment of the binary search range.

Common Pitfalls or Variants

Common pitfalls

Failing to sort positions before placement leads to incorrect feasibility checks.
Assuming the maximum force occurs between consecutive baskets rather than using binary search over the answer space.
Incorrectly updating the binary search range by not considering that smaller distances are always feasible once a larger distance works.

Follow-up variants

Instead of maximizing the minimum force, minimize the maximum force between balls in baskets.
Allow balls to be placed in non-integer positions and compute the optimal minimum distance.
Change the force function from |x - y| to a custom metric and use the same binary search pattern.

FAQ

What is the main strategy to solve Magnetic Force Between Two Balls?

The core strategy is binary search over the valid minimum distances and using greedy placement to verify feasibility.

Why is sorting the positions necessary?

Sorting ensures you can check ball placements sequentially, which is essential for greedy feasibility checks and correct binary search results.

Can we directly try all distances between baskets?

Directly testing all distances is inefficient; binary search reduces the problem to O(n log(max_distance)) time, handling large inputs efficiently.

How does the pattern 'binary search over the valid answer space' apply here?

Instead of searching positions, you search the possible minimum forces and verify each with greedy placement, exactly matching this pattern.

What common mistakes should I avoid in this problem?

Do not skip sorting, incorrectly update the binary search range, or assume any arbitrary basket pairs determine the maximum force.

terminal

Solution

Solution 1: Binary Search

We notice that the greater the minimum magnetic force between any two balls, the fewer balls can be placed, which exhibits monotonicity. We can use binary search to find the maximum minimum magnetic force that allows the number of balls not less than $m$ to be placed.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(f: int) -> bool:
            prev = -inf
            cnt = 0
            for curr in position:
                if curr - prev >= f:
                    prev = curr
                    cnt += 1
            return cnt < m

        position.sort()
        l, r = 1, position[-1]
        return bisect_left(range(l, r + 1), True, key=check)

Continue Practicing

#1508 range sum of sorted subarray sums #1498 number of subsequences that satisfy the given sum condition #1608 special array with x elements greater than or equal x