Log inSign up
mediumleetcodeNot Started

Magnetic Force Between Two Balls

In the universe Earth C-137, Rick has n empty baskets at positions position[i]. Given m balls, distribute all m balls into baskets such that the minimum magnetic force between any two balls is maximized.

Binary Search
Solve on leetcode
Lesson

Problem Statement

In the universe Earth C-137, Rick discovers a special form of magnetic force between two balls if they are put in his new invention. Rick has n empty baskets, the ith basket is at position[i], Rick 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 defines the magnetic force between two different balls at positions x and y as |x - y|.

Given the integer array position and the integer m. Return the required maximum minimum magnetic force.

Example 1 · Example 1: Standard Case:

Input: position = [1, 2, 3, 4, 7], m = 3
Output: 3
Explanation: Placing 3 balls at positions 1, 4, and 7 gives distances |1-4|=3, |4-7|=3, |1-7|=6. Minimum force is 3.

Example 2 · Example 2: Dense Array:

Input: position = [5, 4, 3, 2, 1, 1000000000], m = 2
Output: 999999999
Explanation: Placing balls at 1 and 1000000000 gives force 999999999.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate minimax distance problems as binary search on answer.
  • Prove why greedy first-position placement is optimal.
  • Achieve optimal time complexity with in-place sorting.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximize the minimum distance / force between k placed objects.
  • Monotonic feasibility: if distance d is possible, any distance < d is also possible.
  • Greedy placement works after sorting.

Algorithmic Decision Tree:

  • Sort position.
  • low = 1, high = position[n - 1] - position[0], ans = 1.
  • While low <= high: mid = low + (high - low) / 2.
  • If canPlace(mid, m) -> ans = mid, low = mid + 1.
  • Else high = mid - 1.
  • Return ans.

Connected Patterns:

Aggressive Cows (identical problem)Koko Eating BananasCapacity To Ship Packages

1. Linear Distance Increment

Intuition

Sort position array. Test every distance d starting from 1 upwards. Return d - 1 when canPlace(d, m) becomes false.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Sort position array.
  2. Step 2: Loop d from 1 to position[n-1] - position[0].
  3. Step 3: If canPlace(d, m) is false, return d - 1.
  4. Step 4: Return max possible distance.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDistance(vector<int>& position, int m) {
10 sort(position.begin(), position.end());
11 int maxDist = position.back() - position.front();
12 for (int d = 1; d <= maxDist; ++d) {
13 int count = 1, last = position[0];
14 for (int i = 1; i < (int)position.size(); ++i) {
15 if (position[i] - last >= d) {
16 count++;
17 last = position[i];
18 }
19 }
20 if (count < m) return d - 1;
21 }
22 return maxDist;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log n + n * (max_pos - min_pos)) — Sorting takes O(n log n), then up to 109 distance checks taking O(n) each.
  • Space complexity: O(1) — O(1) auxiliary space.

2. Jump Search on Distance Domain

Intuition

Advance distance d in jumps of step size S. Once placement fails, linear search backwards in the last interval of size S.

When to apply: When distance domain is moderately sized.

Algorithm

  1. Step 1: Sort position array.
  2. Step 2: Advance d in jumps of S until canPlace(d, m) fails.
  3. Step 3: Linear scan interval [d - S, d] for highest feasible value.
  4. Step 4: Return maximum feasible distance.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDistance(vector<int>& position, int m) {
10 sort(position.begin(), position.end());
11 int maxDist = position.back() - position.front();
12 int step = max(1, (int)sqrt(maxDist));
13 int d = 1;
14 auto canPlace = [&](int dist) {
15 int count = 1, last = position[0];
16 for (int i = 1; i < (int)position.size(); ++i) {
17 if (position[i] - last >= dist) {
18 count++;
19 last = position[i];
20 }
21 }
22 return count >= m;
23 };
24 while (d <= maxDist && canPlace(d)) d += step;
25 for (int i = d; i >= max(1, d - step); --i) {
26 if (canPlace(i)) return i;
27 }
28 return 1;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n log n + n * sqrt(max_dist)) — Reduces distance queries by sqrt factor.
  • Space complexity: O(1) — O(1) memory.

3. Binary Search on Answer (Max-Min Distance)

Intuition

Sort position. Set low = 1, high = position[n - 1] - position[0], ans = 1. While low <= high, compute mid. If canPlace(mid, m) is true, record ans = mid and try larger distance (low = mid + 1); else high = mid - 1.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: Sort position in ascending order.
  2. Step 2: low = 1, high = position[n - 1] - position[0], ans = 1.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - count = 1, last = position[0].
  6. - For i = 1 to n - 1: if position[i] - last >= mid { count++; last = position[i]; }.
  7. - If count >= m: ans = mid, low = mid + 1.
  8. - Else high = mid - 1.
  9. Step 4: Return ans.

Trace for position = [1, 2, 3, 4, 7], m = 3

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [1, 6]
Visual state
Values and pointers at this exact step
pointers
S
Ball 1
Empty
Empty
Ball 2
Ball 3
0
↑ low
1
2
↑ mid
3
4
↑ high
Check / comparison
At distance 3: placed 3 balls >= 3 -> Feasible.
Decision / next transition
Record ans = 3, set low = 4.
Why this step matters

Range [1, 6]. mid=3. Greedily place: Ball 1 at pos 1. Next >= 1+3=4 is pos 4 (Ball 2). Next >= 4+3=7 is pos 7 (Ball 3). Placed 3 balls >= m (3). Feasible! ans=3. Search right: low = mid + 1 = 4.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDistance(vector<int>& position, int m) {
10 sort(position.begin(), position.end());
11 int low = 1, high = position.back() - position.front();
12 int ans = 1;
13 while (low <= high) {
14 int mid = low + (high - low) / 2;
15 int count = 1, last = position[0];
16 for (int i = 1; i < (int)position.size(); ++i) {
17 if (position[i] - last >= mid) {
18 count++;
19 last = position[i];
20 }
21 }
22 if (count >= m) {
23 ans = mid;
24 low = mid + 1;
25 } else {
26 high = mid - 1;
27 }
28 }
29 return ans;
30 }
31};
32
33int main() {
34 // Sample driver execution
35 cout << "Execution completed successfully." << endl;
36 return 0;
37}
38

Time & Space Complexity

  • Time complexity: O(n log n + n * log(max_dist)) — Sorting takes O(n log n). Binary search takes at most 30 iterations of O(n) greedy check.
  • Space complexity: O(1) — Sorts in-place with O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Distance IncrementO(n log n + n * range)O(1)Test distances 1, 2, 3... sequentially.Iterates through entire coordinate range.
2.Jump SearchO(n log n + n * sqrt(range))O(1)Jump in blocks of size sqrt(range).Linear stepping within interval.
3.Binary Search on AnswerOptimalO(n log n + n * log(range))O(1)Binary search on monotonic distance domain.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • m == 2 -> distance is simply position[n-1] - position[0].
  • m == n -> distance is minimum adjacent difference min(position[i] - position[i-1]).
  • Large coordinates (109) -> handled effortlessly by O(log(109)) = 30 steps.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why sorting position is required before greedy simulation.
  2. Prove greedy choice: placing a ball at the earliest valid position leaves the maximum remaining room for future balls.
  3. State equivalence to the famous 'Aggressive Cows' problem.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it always optimal to place the very first ball in the first sorted basket position[0]?

Back to DSA Sheet