DSA sheet · Binary Search · Binary search on answer (max of min)

Magnetic Force Between Two Balls

Balls are dropped into baskets along a line, and the force between two balls depends on how far apart they are. We want the weakest pull (the closest pair of balls) to be as far apart as possible. The teacher says straight away that this is the Aggressive Cows problem with new names: stalls become baskets and cows become balls. She builds the brute force (try every gap), runs it to show the TLE on LeetCode, and then switches the outer loop to binary search on the answer.

Why it matters: seeing the same idea under a different story is how you learn to recognise the pattern. Her closing advice: binary search on answer comes down to four jobs: find low, find high, write the check function, and decide which way to move.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every gap one by one
• Part B · Optimal: binary search on the gap
• Part C · Revision page

Part 0 · Before starting

Normal binary search in one paragraph

Binary search needs something sorted, or more generally a yes/no question whose answer changes only once as you move left to right. Keep two ends, low and high, test the middle mid, and throw away the half that can't contain the answer. The range halves every step, so it takes about log₂(size) steps.

How to compute mid, and why that form

mid = low + (high - low) // 2

This equals (low + high) // 2, but in Java or C++ the sum low + high can be bigger than the largest int (2³¹ − 1 ≈ 2.1 × 10⁹) and turn into garbage. The teacher points to this problem's numbers: positions go up to 10⁹, so high can be close to 10⁹, and she prefers the safe form "whenever the constraints are big". Python integers never overflow, so in Python both forms give the right number. We keep the safe form as a habit.

The pattern: binary search on the answer

1. Answer range: the smallest answer that could make sense (low) and the largest (high).
2. Yes/no check: a function that tests one candidate answer: "with this value, is it possible?"
3. Monotonic: along the range, all the yeses are on one side and all the noes on the other. So one test at mid tells us which half to drop.

The hint that you're in this pattern: the answer is a number like a distance, a speed or a sum that is not picked from the array, and the wording is "maximum of the minimum" or "minimum of the maximum".

Maximise the minimum vs minimise the maximum

Part A · Brute force: try every gap one by one

LeetCode 1552

1The question in simple words

The array position lists where the baskets are on a line. All positions are different. We have m balls, at most one per basket. The magnetic force between two balls is just their distance. Place all m balls so that the smallest distance between any two of them is as large as possible, and return that distance.

Example 1: position = [1, 2, 3, 4, 7], m = 3 → answer 3.

line:  1  2  3  4  .  .  7
best:  B        B        B      gaps 3 and 3 → smallest = 3
weak:  B  B  B                  gaps 1 and 1 → smallest = 1

Balls at 1, 2, 3 all fit, but they're only 1 apart, which is a strong force. Balls at 1, 4, 7 are 3 apart both times. We can't do better, so the answer is 3. Like the teacher says, we must push the balls as far apart as we can, then report the minimum gap of that best placement.

Example 2: position = [5, 4, 3, 2, 1, 1000000000], m = 2 → answer 999999999 (one ball at 1, one at 10⁹). Notice the input isn't sorted.

2What the constraints tell us

• n (number of baskets) from 2 to 10⁵. A walk over the baskets costs up to 10⁵.
• position[i] from 1 to 10⁹, all different. So the gap between the two farthest baskets can be almost 10⁹. That's how many gaps the brute force might have to try.
• m from 2 to n. There are at least two balls, so a distance always exists, and the balls always fit somewhere. The answer is always at least 1.
• About 10⁸ simple steps is the TLE limit the teacher uses.

3Intuition

Flip the question: "if every two balls must be at least g apart, can I still place all m balls?" That's a yes/no question we can answer with one walk along the line. Try g = 1, 2, 3, … and keep the largest g that says yes.

4Building the logic from examples

The teacher tries each gap on [1, 2, 3, 4, 7], m = 3

• gap 1: balls at 1, 2, 3 → all 3 placed → yes.
• gap 2: ball at 1. 2 is too close. 3 is 2 away → ball. 4 is 1 from 3 → too close. 7 is 4 from 3 → ball. Balls at 1, 3, 7 → yes.
• gap 3: ball at 1. 2 and 3 are too close. 4 is 3 away → ball. 7 is 3 from 4 → ball. Balls at 1, 4, 7 → yes.
• gap 4: ball at 1. 2, 3, 4 are all too close (at most 3 away). 7 is 6 away → ball. No baskets left. Only 2 balls → no.

The yes/no line over all gaps

low = 1

All balls can't share one basket (one ball per basket), so two balls are at least 1 apart. The smallest gap worth trying is 1.

high = max position − min position

The teacher first wonders whether high should be "infinity" or 10⁹. Then she uses the smallest m, which is 2: with only two balls, you put one at each end. That gives the biggest distance possible, 7 − 1 = 6 here. More balls can only bring the closest pair nearer. So high = max − min, and after sorting that's position[-1] - position[0].

Why sort the positions?

Example 2 is not sorted. After sorting, the check can walk left to right and only look at the next basket: if it's too close, move on, and the ones after it will be farther. Without sorting, a "too close" basket doesn't tell you anything about the rest, so for every ball you'd need another loop over all baskets to find a valid one. One sort up front is the cheapest option. Sorting also makes last − first equal to max − min.

The check: canPlace(position, m, gap)

• The first ball goes in the first basket: count = 1, last = position[0].
• For each next basket: if position[i] - last >= gap, put a ball there, count += 1, and set last = position[i].
• At the end: count >= m → yes. If we could fit more than m balls, that's fine too (we just use m of them).

Scanning the gaps: save on yes, stop on the first no

Going up from gap 1: gap 1 says yes, but it's not the largest, so don't return it. Save it in answer. Gap 2 → save 2. Gap 3 → save 3. Gap 4 → no. Now answer still holds 3, and every bigger gap will also say no, so break and return 3.

Or go down from high: 6 no, 5 no, 4 no, 3 yes → return 3 immediately. The first yes from the top is the largest, so no answer variable is needed.

5Approach steps

1. Sort position.
2. low = 1, high = position[-1] - position[0].
3. For gap = low … high: if canPlace says yes, answer = gap; else break.
4. Return answer.

6Code (Python)

class Solution:
    def maxDistance(self, position, m):
        position.sort()
        low = 1
        high = position[-1] - position[0]
        answer = 0
        for gap in range(low, high + 1):
            if self.canPlace(position, m, gap):
                answer = gap         # possible: save and try bigger
            else:
                break                # first "no": bigger gaps fail too
        return answer

    def canPlace(self, position, m, gap):
        count = 1                    # first ball in the first basket
        last = position[0]
        for i in range(1, len(position)):
            if position[i] - last >= gap:
                count += 1
                last = position[i]
                if count >= m:       # already placed enough, stop early
                    return True
        return count >= m

7Code line by line

8Dry run (hand table)

position = [1, 2, 3, 4, 7], m = 3. low = 1, high = 6.

Return 3 ✓.

What happens on Example 2: high = 10⁹ − 1, and every gap up to that says yes (two balls at the two ends). So the loop really does run about 10⁹ times. The teacher shows that the code runs fine on Example 1 if you cap high at 10³ (10³ × 10⁵ = 10⁸ steps), but on submit, Example 2 alone gives TLE.

9Complexity & remember

• Time: up to 10⁹ gaps × a 10⁵ walk = 10¹⁴ steps → TLE. (Plus O(n log n) for sorting.)
• Space: O(1) extra.

The walk over the baskets must stay, because each basket has to be looked at. But the gaps 1, 2, …, high are a sorted number line with one Y→N flip, so we can binary search over them.

Part B · Optimal: binary search on the gap

1The question

Same problem, same low, high and canPlace. We only change how we pick which gap to test: always the middle of what's left.

2Constraints

Same as Part A. log₂(10⁹) ≈ 30, so about 30 checks instead of 10⁹.

3Intuition

The line is Y Y Y N N N and we want the last Y. The teacher's reasoning: when gap 1 worked, we looked at 2. When 2 worked, we looked at 3. So a yes always sends us toward bigger gaps.

• check(mid) yes → save mid, search the right half: low = mid + 1.
• check(mid) no → mid and everything bigger fail, so search the left half: high = mid - 1.

4Building the logic

The answer range shrinking (Example 1)

5Approach steps

1. Sort. low = 1, high = position[-1] - position[0], answer = 0.
2. While low <= high: mid = low + (high - low) // 2.
3. canPlace(mid) yes → answer = mid, low = mid + 1. No → high = mid - 1.
4. Return answer.

6Code (Python)

class Solution:
    def maxDistance(self, position, m):
        position.sort()
        low = 1
        high = position[-1] - position[0]
        answer = 0
        while low <= high:
            mid = low + (high - low) // 2      # candidate minimum gap
            if self.canPlace(position, m, mid):
                answer = mid                   # possible: save it
                low = mid + 1                  # look for a bigger gap
            else:
                high = mid - 1                 # too big: look smaller
        return answer

    def canPlace(self, position, m, gap):
        count = 1
        last = position[0]
        for i in range(1, len(position)):
            if position[i] - last >= gap:
                count += 1
                last = position[i]
                if count >= m:
                    return True
        return count >= m

7Code line by line

8Dry run (hand table)

position = [1, 2, 3, 4, 7], m = 3.

Example 2 (sorted: 1, 2, 3, 4, 5, 10⁹; m = 2): every mid says yes (the two ends are always far enough apart), so low keeps moving right, and after about 30 steps answer = high = 999999999 ✓.

9Complexity & remember

• Time O(n log n + n · log(max − min)): about 30 checks × 10⁵ = 3 × 10⁶, plus the sort. The teacher calls it the fastest solution.
• Space O(1) extra.

Part C · Revision page

s = Solution()
print(s.maxDistance([1, 2, 3, 4, 7], 3))                 # 3
print(s.maxDistance([5, 4, 3, 2, 1, 1000000000], 2))     # 999999999
print(s.maxDistance([1, 2], 2))                          # 1
print(s.maxDistance([79, 74, 57, 22], 4))                # 5

Run the second line with the binary search version only. The brute force would try about 10⁹ gaps there, which is exactly the TLE from the video.

Based on this video: Magnetic Force Between Two Balls | Binary Search on Answer