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.
The problem can be solved efficiently using a binary search on the minimum magnetic force. Start by sorting the basket positions, then perform a binary search to find the maximum valid minimum force. The basic idea is to check if it is possible to place all the balls with at least a certain minimum distance (force) between any two of them. If it is possible, try for a larger minimum distance, otherwise try smaller.
This C solution implements a binary search method to find the maximum minimum force. We first sort the basket positions, then binary search for the largest possible minimum distance using a helper function `canPlaceBalls` which checks if we can place all balls with at least `minDist` distance apart.
Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets.
Space Complexity: O(1)
This approach involves using a binary search for determining the optimal force, aided by a greedy strategy to verify if a particular minimum force is attainable. By iterating over the sorted positions, balls are placed as far apart as possible greedily.
This C approach employs a binary search over potential forces while utilizing a greedy method to check if balls can be spaced with at least the current middle value as the force. The `canPlaceBalls` function iterates to find feasible placement for balls.
Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets.
Space Complexity: O(1)
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.
First, we sort the positions of the baskets, and then use binary search with the left boundary l = 1 and the right boundary r = position[n - 1], where n is the number of baskets. In each binary search iteration, we calculate the midpoint m = (l + r + 1) / 2, and then determine if there is a way to place the balls such that the number of balls placed is not less than m.
The problem is transformed into determining whether a given minimum magnetic force f can place m balls. We can traverse the positions of the baskets from left to right, and if the distance between the position of the last ball and the current basket's position is greater than or equal to f, it indicates that a ball can be placed in the current basket. Finally, we check if the number of balls placed is not less than m.
The time complexity is O(n times log n + n times log M), and the space complexity is O(log n). Here, n and M respectively represent the number of baskets and the maximum value of the basket positions.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Binary Search on Answer | Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets. |
| Greedy with Binary Search | Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets. |
| Binary Search | — |
| 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 |
Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIK • codestorywithMIK • 13,716 views views
Watch 9 more video solutions →Practice Magnetic Force Between Two Balls with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor