Binary Search on Answer Explained – LeetCode 1552 (Magnetic Force Between Two Balls)

Binary Search on Answer – LeetCode 1552 Explained

LeetCode 1552 (Magnetic Force Between Two Balls) is a classic problem that teaches the Binary Search on Answer pattern. This problem may not look like a binary search problem at first glance, but once the intuition clicks, the solution becomes very elegant.

🔍 Problem Summary

You are given an array position representing positions on a line. You must place m balls such that the minimum distance between any two balls is as large as possible.

🧠 Key Insight

Instead of placing balls directly, we ask a better question:

Can we place m balls if the minimum distance between each ball is at least d?

This question has a monotonic behavior:

• If distance d is possible, then any smaller distance is also possible.
• If distance d is not possible, then any larger distance is impossible.

This monotonic nature allows us to apply binary search on the answer.

⚙️ Greedy Validation Function

To validate a distance, we greedily place balls from left to right, always placing the next ball as early as possible.

def possible(position, m, dist):
    placed = 1
    prev = position[0]

    for i in position:
        if i - prev >= dist:
            placed += 1
            prev = i

    return placed >= m
  

If we can place at least m balls, then the distance is feasible.

🔁 Binary Search on Distance

We now binary search on the range of possible distances:

• Minimum distance = 1
• Maximum distance = position[-1] - position[0]

A common pitfall here is using (l + r) // 2, which can cause an infinite loop when searching for the maximum valid value. To avoid this, we use a right-biased mid.

class Solution:
    def possible(self, position, m, mid):
        placed = 1
        prev = position[0]

        for i in position:
            if i - prev >= mid:
                placed += 1
                prev = i

        return placed >= m

    def maxDistance(self, position, m):
        position.sort()
        l = 1
        r = position[-1] - position[0]

        while l < r:
            mid = (l + r + 1) // 2
            if self.possible(position, m, mid):
                l = mid
            else:
                r = mid - 1

        return l
  

🚫 Why (l + r + 1) // 2?

Since we are maximizing the distance, we must ensure progress. Using a right-biased mid prevents cases where l never moves forward, which would otherwise cause an infinite loop.

📊 Complexity Analysis

• Time: O(n log(max_distance))
• Space: O(1)

📂 Source Code

Full Python implementation is available on GitHub:

👉 View LC1552.py on G