Magnetic Force Between Two Balls
Binary search the ANSWER, then greedily test it
Nothing in the basket list is the answer, so there is no cell to search for. Turn it around and ask a yes/no question instead: can the balls be placed with every pair at least d apart? A left-to-right greedy answers that in one pass, and the answers are monotonic — if d works, every smaller gap works, and once d fails every larger gap fails too. That yes/no flip is exactly the sorted-true-then-false shape binary search needs, so we search d itself and keep the largest d that still answers yes.
Details
Animated on: position = 29, 1, 41, 20, 58, 12, 70, 5 and m = 4 balls. Drop at most one ball per basket so that the smallest distance between any two balls is as large as possible.
Problem:Magnetic Force Between Two BallsMedium
Binary search the ANSWER, then greedily test it
step 1 / 10
8 baskets at 29, 1, 41, 20, 58, 12, 70, 5 and 4 balls to drop in. Balls pull on each other harder the closer they are, so we want the placement where the CLOSEST pair of balls is as far apart as possible.
1FUNCTION maxMinDistance(position, m):2 position <- SORT(position)3 low <- 14 high <- position[LENGTH(position) - 1] - position[0]5 WHILE low <= high6 mid <- (low + high) / 27 IF canPlace(position, m, mid)8 best <- mid9 low <- mid + 110 ELSE11 high <- mid - 112 RETURN best
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- 8 baskets at 29, 1, 41, 20, 58, 12, 70, 5 and 4 balls to drop in. Balls pull on each other harder the closer they are, so we want the placement where the CLOSEST pair of balls is as far apart as possible.
- Sorted: 1, 5, 12, 20, 29, 41, 58, 70. Distances only make sense along a line, so sorting first means a ball's neighbour is always the previous basket we used, so there is no need to compare against every other ball.
- We search the ANSWER, not the array: the smallest gap worth trying is 1, the largest is 70 - 1 = 69. A gap that works means every smaller gap works too, so this range is monotonic and binary search applies.
- Try gap 35: walking left to right and grabbing the first basket at least 35 past the last ball runs out after only 2 of the 4 balls (1, 41). Taking the earliest legal basket every time never wastes one, so if that walk cannot fit them nothing can — 35 is too ambitious, and so is every larger gap, high becomes 34.
- Try gap 17: walking left to right and grabbing the first basket at least 17 past the last ball fits all 4 balls at 1, 20, 41, 58. So 17 is genuinely reachable — bank it as the best so far and get greedier, low becomes 18.
- Try gap 26: walking left to right and grabbing the first basket at least 26 past the last ball runs out after only 3 of the 4 balls (1, 29, 58). Taking the earliest legal basket every time never wastes one, so if that walk cannot fit them nothing can — 26 is too ambitious, and so is every larger gap, high becomes 25.
- Try gap 21: walking left to right and grabbing the first basket at least 21 past the last ball runs out after only 3 of the 4 balls (1, 29, 58). Taking the earliest legal basket every time never wastes one, so if that walk cannot fit them nothing can — 21 is too ambitious, and so is every larger gap, high becomes 20.
- Try gap 19: walking left to right and grabbing the first basket at least 19 past the last ball fits all 4 balls at 1, 20, 41, 70. So 19 is genuinely reachable — bank it as the best so far and get greedier, low becomes 20.
- Try gap 20: walking left to right and grabbing the first basket at least 20 past the last ball runs out after only 3 of the 4 balls (1, 29, 58). Taking the earliest legal basket every time never wastes one, so if that walk cannot fit them nothing can — 20 is too ambitious, and so is every larger gap, high becomes 19.
- low 20 has passed high 19, so the range is exhausted. Put the balls at 1, 20, 41, 70 — the closest two are 19 apart, and no placement does better.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.