Magnetic Force Between Two Balls — Problem & Solution
Magnetic Force Between Two Balls solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Magnetic Force Between Two Balls is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Baskets sit at the distinct coordinates in position. You place m balls into distinct baskets. The magnetic force between two balls is the distance between their baskets.
Maximise the minimum magnetic force between any two balls, and return that value.
Example 1
Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Balls at 1, 4 and 7 are 3 apart at the closest.
Example 2
Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: Put them at the extremes.
Example 3
Input: position = [1,2,3,4,5], m = 5
Output: 1
Constraints
2 <= position.length <= 1000001 <= position[i] <= 1000000000All positions are distinct.2 <= m <= position.length
Hints for Magnetic Force Between Two Balls
Hint 1
If a minimum gap
dis achievable, so is every smaller gap — the feasibility is monotone.Hint 2
Binary search
d; for a candidate, greedily place a ball at the first basket and then at every basket at leastdbeyond the last one used.Hint 3
Sort the positions first so 'the next basket far enough away' is well defined.
How to solve Magnetic Force Between Two Balls
Binary search the answer. For a fixed minimum gap d, the greedy leftmost placement fits the maximum possible number of balls, so it decides feasibility exactly.
Approach
- Sort the positions.
can(d): start at the leftmost basket, then walk right and take a basket whenever it is at leastdbeyond the last taken one; feasible when at leastmballs fit.- Binary search the largest feasible
d, with the upper-biased midpoint so the loop terminates.
Why it works
The greedy is optimal because placing a ball as early as possible leaves the most room for the rest — an exchange argument moves any optimal solution's first ball to the leftmost basket without loss. Raising d can only reduce how many balls fit, so can is monotone decreasing and the boundary is what binary search finds.
Complexity
- Time —
O(n log n + n log P) where P is the coordinate range - Space —
O(n)
Pitfalls
- The upper-biased midpoint
ceil((lo + hi) / 2)is required for a 'largest satisfying value' search; the plain midpoint loops forever. - Comparing with
>instead of>=insidecanrejects placements exactlydapart. - The positions arrive unsorted.
Reference solution
Python
from typing import List
def maxDistance(position: List[int], m: int) -> int:
p = sorted(position)
def can(d: int) -> bool:
cnt, last = 1, p[0]
for x in p[1:]:
if x - last >= d:
cnt += 1
last = x
return cnt >= m
lo, hi = 1, p[-1] - p[0]
while lo < hi:
mid = (lo + hi + 1) // 2
if can(mid):
lo = mid
else:
hi = mid - 1
return loJava
private static boolean canPlaceBalls(int[] p, int m, int d) {
int cnt = 1, last = p[0];
for (int i = 1; i < p.length; i++) {
if (p[i] - last >= d) {
cnt++;
last = p[i];
}
}
return cnt >= m;
}
public static int maxDistance(int[] position, int m) {
int[] p = position.clone();
Arrays.sort(p);
int lo = 1, hi = p[p.length - 1] - p[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlaceBalls(p, m, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}C++
static bool canPlaceBalls(vector<int>& p, int m, int d) {
int cnt = 1, last = p[0];
for (int i = 1; i < (int) p.size(); i++) {
if (p[i] - last >= d) {
cnt++;
last = p[i];
}
}
return cnt >= m;
}
int maxDistance(vector<int>& position, int m) {
vector<int> p = position;
sort(p.begin(), p.end());
int lo = 1, hi = p.back() - p.front();
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlaceBalls(p, m, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}JavaScript
var maxDistance = function(position, m) {
var p = position.slice().sort(function(a, b) { return a - b; });
var can = function(d) {
var cnt = 1, last = p[0];
for (var i = 1; i < p.length; i++) {
if (p[i] - last >= d) { cnt++; last = p[i]; }
}
return cnt >= m;
};
var lo = 1, hi = p[p.length - 1] - p[0];
while (lo < hi) {
var mid = Math.ceil((lo + hi) / 2);
if (can(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms