Magnetic Force Between Two Balls
Magnetic Force Between Two Balls is a medium binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the gap), runs in O(n log n + n log R) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every gap) up.
Problem
There are n baskets on a straight line; basket i sits at coordinate position[i]. You must drop m balls into m different baskets.
Two balls at coordinates x and y repel each other with a force of |x - y|. Choose the baskets so that the smallest force between any two balls is as large as possible, and return that smallest force.
Examples
Example 1
- Input
position = [2, 9, 4, 13, 7], m = 3- Output
5- Why
- Sorted baskets are [2, 4, 7, 9, 13]. Putting balls at 2, 7 and 13 gives gaps 5 and 6, so the smallest gap is 5. No placement does better.
Example 2
- Input
position = [10, 1, 100, 50], m = 4- Output
9- Why
- Every basket gets a ball, so the answer is the smallest gap between neighbours: 10 - 1 = 9.
Example 3
- Input
position = [3, 30], m = 2- Output
27- Why
- Two balls go to the two ends.
Constraints
2 <= position.length <= 10^51 <= position[i] <= 10^9- All values in
positionare distinct. 2 <= m <= position.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every gap) | O(n log n + A·n) | O(1) |
| Optimal (binary search on the gap) | O(n log n + n log R) | O(1) |
1Brute force (try every gap)
O(n log n + A·n)Sorting, then one O(n) greedy check for every gap value up to the answer A, which can be as large as 10^9.O(1)Only a few counters besides the sort.Sort the baskets. Try gaps d = 1, 2, 3, … and for each one run the greedy placement. The last d that still fits all m balls is the answer.
- Sort
position. - Write
canPlace(d): place a ball at the first basket, then walk right and place a ball whenever the distance to the last ball is at least d. Return true once m balls are placed. - Start with d = 1 and increase it while
canPlace(d)is true; remember the last true d.
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int best = 0;
for (int d = 1; canPlace(position, m, d); d++) {
best = d;
}
return best;
}
private boolean canPlace(int[] p, int m, int gap) {
int count = 1;
int last = p[0];
for (int i = 1; i < p.length && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}
}class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
position.sort()
best = 0
d = 1
while self.canPlace(position, m, d):
best = d
d += 1
return best
def canPlace(self, p: List[int], m: int, gap: int) -> bool:
count = 1
last = p[0]
for i in range(1, len(p)):
if count >= m:
break
if p[i] - last >= gap:
count += 1
last = p[i]
return count >= mclass Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
int best = 0;
for (int d = 1; canPlace(position, m, d); d++) {
best = d;
}
return best;
}
private:
bool canPlace(const vector<int>& p, int m, int gap) {
int count = 1;
int last = p[0];
for (int i = 1; i < (int)p.size() && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}
};function maxDistance(position, m) {
position.sort((a, b) => a - b);
let best = 0;
for (let d = 1; canPlace(position, m, d); d++) {
best = d;
}
return best;
}
function canPlace(p, m, gap) {
let count = 1;
let last = p[0];
for (let i = 1; i < p.length && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}2Optimal (binary search on the gap)
O(n log n + n log R)Sorting, then about log2(10^9) ≈ 30 greedy checks of O(n) each (R = max - min).O(1)Only the search bounds and the counters of the check (plus whatever the sort uses).The answer lies between 1 and (max - min) / (m - 1). Feasibility is monotonic: if gap d works, any smaller gap works too. So binary search for the largest d where the greedy placement still fits m balls.
- Sort
position. - Set lo = 1 and hi = (last - first) / (m - 1), the best gap you could ever hope for.
- While lo < hi: take mid = lo + (hi - lo + 1) / 2 (round up so the loop always moves).
- If
canPlace(mid)is true, the answer is at least mid: lo = mid. Otherwise hi = mid - 1. - Return lo.
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int n = position.length;
int lo = 1, hi = (position[n - 1] - position[0]) / (m - 1);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlace(position, m, mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
private boolean canPlace(int[] p, int m, int gap) {
int count = 1;
int last = p[0];
for (int i = 1; i < p.length && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}
}class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
position.sort()
lo, hi = 1, (position[-1] - position[0]) // (m - 1)
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if self.canPlace(position, m, mid):
lo = mid
else:
hi = mid - 1
return lo
def canPlace(self, p: List[int], m: int, gap: int) -> bool:
count = 1
last = p[0]
for x in p:
if x - last >= gap:
count += 1
last = x
if count >= m:
return True
return count >= mclass Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
int n = position.size();
int lo = 1, hi = (position[n - 1] - position[0]) / (m - 1);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlace(position, m, mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
private:
bool canPlace(const vector<int>& p, int m, int gap) {
int count = 1;
int last = p[0];
for (int i = 1; i < (int)p.size() && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}
};function maxDistance(position, m) {
position.sort((a, b) => a - b);
const n = position.length;
let lo = 1, hi = Math.floor((position[n - 1] - position[0]) / (m - 1));
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2);
if (canPlace(position, m, mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
function canPlace(p, m, gap) {
let count = 1;
let last = p[0];
for (let i = 1; i < p.length && count < m; i++) {
if (p[i] - last >= gap) {
count++;
last = p[i];
}
}
return count >= m;
}Edge cases to test
m == 2: the answer is simply max - minm == n: every basket is used, the answer is the smallest neighbour gap- The input is not sorted
- Huge coordinates where
max - minis close to 10^9
Hints
Hint 1
Sort the positions first. If you fix a minimum gap d, can you check quickly whether m balls fit?
Hint 2
Greedy check: put the first ball in the leftmost basket and every next ball in the first basket at least d away from the previous one.
Hint 3
If gap d is achievable then every smaller gap is too. That monotonic yes/no lets you binary search d.
FAQ
What is the best time complexity for Magnetic Force Between Two Balls?
Optimal (binary search on the gap) runs in O(n log n + n log R) time and O(1) extra space. Sorting, then about log2(10^9) ≈ 30 greedy checks of O(n) each (R = max - min).
Which pattern does Magnetic Force Between Two Balls use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Magnetic Force Between Two Balls?
Yes. Brute force (try every gap) takes O(n log n + A·n) time and O(1) space. Sort the baskets.
Which edge cases should I test for Magnetic Force Between Two Balls?
m == 2: the answer is simply max - min; m == n: every basket is used, the answer is the smallest neighbour gap; The input is not sorted; Huge coordinates where max - min is close to 10^9.