Magnetic Force Between Two Balls

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atAmazonMakeMyTrip

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^5
  • 1 <= position[i] <= 10^9
  • All values in position are 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(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.
SpaceO(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.

  1. Sort position.
  2. 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.
  3. 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;
    }
}

2Optimal (binary search on the gap)

TimeO(n log n + n log R)Sorting, then about log2(10^9) ≈ 30 greedy checks of O(n) each (R = max - min).
SpaceO(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.

  1. Sort position.
  2. Set lo = 1 and hi = (last - first) / (m - 1), the best gap you could ever hope for.
  3. While lo < hi: take mid = lo + (hi - lo + 1) / 2 (round up so the loop always moves).
  4. If canPlace(mid) is true, the answer is at least mid: lo = mid. Otherwise hi = mid - 1.
  5. 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;
    }
}

Edge cases to test

  • 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

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.