Watch 10 video solutions for Magnetic Force Between Two Balls, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by codestorywithMIK has 13,716 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.
Rick stated that magnetic force between two different balls at positions x and y is |x - y|.
Given the integer array position and the integer m. Return the required force.
Example 1:
Input: position = [1,2,3,4,7], m = 3 Output: 3 Explanation: 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 Explanation: We can use baskets 1 and 1000000000.
Constraints:
n == position.length2 <= n <= 1051 <= position[i] <= 109position are distinct.2 <= m <= position.lengthProblem Overview: You are given an array position representing basket coordinates on a line and an integer m for the number of balls. Place the balls so the minimum distance between any two balls is as large as possible. The task is to compute this maximum possible minimum magnetic force.
Approach 1: Binary Search on Answer (O(n log n) time, O(1) space)
The key observation: if a minimum distance d between balls is feasible, then every value smaller than d is also feasible. This monotonic property allows a binary search over the answer. First sort the positions using sorting. Then search the distance range from 1 to position[n-1] - position[0]. For each candidate distance, iterate through the array and greedily place balls whenever the gap from the last placed ball is at least that distance. If you can place m balls, the distance works, so move the binary search right to try a larger distance. Otherwise move left. Each feasibility check scans the array once, giving O(n) per check and O(n log D) overall where D is the coordinate range.
Approach 2: Greedy Placement with Binary Search (O(n log n) time, O(1) space)
This approach focuses on the greedy feasibility check used inside the binary search. After sorting the array, always place the first ball at the smallest coordinate. Continue iterating through baskets and place the next ball in the earliest position that maintains the required minimum distance from the previously placed ball. Greedy works because placing balls earlier leaves maximum space for remaining placements. If the greedy pass successfully places m balls, the tested distance is valid. Combined with binary search over possible distances, this efficiently finds the largest feasible minimum force. Sorting costs O(n log n), and each feasibility pass costs O(n).
Recommended for interviews: Interviewers expect the binary search on answer combined with a greedy feasibility check. A brute-force search over all distances or placements quickly becomes exponential and signals missing insight. Demonstrating the monotonic feasibility condition and using binary search shows strong algorithmic reasoning, especially for optimization problems where the answer space can be searched instead of constructed directly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Answer | O(n log n + n log D) | O(1) | General optimal approach when maximizing a minimum distance or value |
| Greedy Placement with Binary Search | O(n log n) | O(1) | Best when the feasibility check can be verified greedily after sorting |