Magnetic Force Between Two Balls

Medium
817.

Magnetic Force Between Two Balls

Magnetic Force Between Two Balls is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
var maxDistance = function(position, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Magnetic Force Between Two Balls

  1. Hint 1

    If a minimum gap d is achievable, so is every smaller gap — the feasibility is monotone.

  2. Hint 2

    Binary search d; for a candidate, greedily place a ball at the first basket and then at every basket at least d beyond the last one used.

  3. 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

  1. Sort the positions.
  2. 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.
  3. 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

Java

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