Magnetic Force Between Two Balls

medium binary search greedy

Problem

There are n baskets at distinct integer positions along a line, and m balls (2 ≤ m ≤ n) to put into them, one ball per basket. The magnetic force between two balls is simply the distance between their baskets, and the weakest pair determines the overall force. Choose baskets so that this minimum pairwise distance is as large as possible, and return that largest possible minimum force.

Inputposition = [1, 2, 3, 4, 7], m = 3

Output3

Placing balls at positions 1, 4 and 7 gives pairwise distances 3, 3 and 6; the minimum is 3, and no arrangement does better.

position (comma-separated)

m (balls)

def max_distance(position, m):
    position.sort()
    def can_place(gap):
        count, last = 1, position[0]
        for p in position[1:]:
            if p - last >= gap:
                count += 1
                last = p
        return count >= m
    lo, hi, best = 1, position[-1] - position[0], 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_place(mid):
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return best

function maxDistance(position, m) {
  position.sort((a, b) => a - b);
  const canPlace = (gap) => {
    let count = 1, last = position[0];
    for (let i = 1; i < position.length; i++) {
      if (position[i] - last >= gap) {
        count++;
        last = position[i];
      }
    }
    return count >= m;
  };
  let lo = 1, hi = position[position.length - 1] - position[0], best = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (canPlace(mid)) {
      best = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return best;
}

int maxDistance(int[] position, int m) {
    Arrays.sort(position);
    int lo = 1, hi = position[position.length - 1] - position[0], best = 0;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (canPlace(position, m, mid)) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

boolean canPlace(int[] position, int m, int gap) {
    int count = 1, last = position[0];
    for (int i = 1; i < position.length; i++) {
        if (position[i] - last >= gap) {
            count++;
            last = position[i];
        }
    }
    return count >= m;
}

bool canPlace(vector<int>& position, int m, int gap) {
    int count = 1, last = position[0];
    for (int i = 1; i < (int)position.size(); i++) {
        if (position[i] - last >= gap) {
            count++;
            last = position[i];
        }
    }
    return count >= m;
}

int maxDistance(vector<int>& position, int m) {
    sort(position.begin(), position.end());
    int lo = 1, hi = position.back() - position[0], best = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(position, m, mid)) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

Explanation

This is a classic maximize-the-minimum problem, and the key insight is that we do not search positions — we binary search the answer itself. Feasibility is monotone: if all m balls can be placed with every pair at least g apart, then any smaller gap is certainly also achievable, and if g fails, every larger gap fails too. That yes/no boundary is exactly what binary search finds.

The feasibility check is a greedy sweep. Sort the baskets, put the first ball in the leftmost basket, then walk right and drop the next ball into the first basket at least gap away from the previous ball. Placing each ball as far left as legally possible leaves the most room for the remaining balls, so if this greedy cannot fit m balls, nothing can — a standard exchange argument makes that rigorous.

The search window for the gap is [1, position[-1] - position[0]]. Whenever can_place(mid) succeeds we record best = mid and try larger gaps with lo = mid + 1; when it fails we shrink with hi = mid - 1. The loop ends with best holding the largest feasible gap.

Walk through position = [1,2,3,4,7], m = 3. Window is [1, 6]. Try mid = 3: greedy places balls at 1, 4, 7 — three balls fit, so best = 3 and lo = 4. Try mid = 5: only 1 and 7 work, infeasible, hi = 4. Try mid = 4: again only 1 and 7, hi = 3. Now lo > hi and the answer is 3.

Each feasibility check is one pass over the sorted baskets, O(n), and the binary search runs O(log W) times where W is the distance between the outermost baskets. With the initial sort the total is O(n log n + n log W), using only constant extra space.

Time: O(n log n + n log W) Space: O(1)