Magnetic Force Between Two Balls — Medium Problem & Solution

Baskets sit at the distinct coordinates in position. You place m balls into distinct baskets.

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, 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 <= 100000
1 <= position[i] <= 1000000000
All positions are distinct.
2 <= m <= position.length

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 least d beyond the last taken one; feasible when at least m balls 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 >= inside can rejects placements exactly d apart.
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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue