Skip to main content
Talentd

Magnetic Force Between Two Balls - Solution & Explanation

MediumArrayBinary SearchSorting25 min readAsked at: Amazon, Microsoft, Goldman Sachs +6
Practice this problem

Problem Statement

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

 

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

 

Constraints:

  • n == position.length
  • 2 <= n <= 105
  • 1 <= position[i] <= 109
  • All integers in position are distinct.
  • 2 <= m <= position.length

Approach Overview

Problem Overview: You are given an array position representing basket coordinates on a line and an integer m for the number of balls. Place the balls so the minimum distance between any two balls is as large as possible. The task is to compute this maximum possible minimum magnetic force.

Approach 1: Binary Search on Answer (O(n log n) time, O(1) space)

The key observation: if a minimum distance d between balls is feasible, then every value smaller than d is also feasible. This monotonic property allows a binary search over the answer. First sort the positions using sorting. Then search the distance range from 1 to position[n-1] - position[0]. For each candidate distance, iterate through the array and greedily place balls whenever the gap from the last placed ball is at least that distance. If you can place m balls, the distance works, so move the binary search right to try a larger distance. Otherwise move left. Each feasibility check scans the array once, giving O(n) per check and O(n log D) overall where D is the coordinate range.

Approach 2: Greedy Placement with Binary Search (O(n log n) time, O(1) space)

This approach focuses on the greedy feasibility check used inside the binary search. After sorting the array, always place the first ball at the smallest coordinate. Continue iterating through baskets and place the next ball in the earliest position that maintains the required minimum distance from the previously placed ball. Greedy works because placing balls earlier leaves maximum space for remaining placements. If the greedy pass successfully places m balls, the tested distance is valid. Combined with binary search over possible distances, this efficiently finds the largest feasible minimum force. Sorting costs O(n log n), and each feasibility pass costs O(n).

Recommended for interviews: Interviewers expect the binary search on answer combined with a greedy feasibility check. A brute-force search over all distances or placements quickly becomes exponential and signals missing insight. Demonstrating the monotonic feasibility condition and using binary search shows strong algorithmic reasoning, especially for optimization problems where the answer space can be searched instead of constructed directly.

Approach 1: Binary Search on Answer

The problem can be solved efficiently using a binary search on the minimum magnetic force. Start by sorting the basket positions, then perform a binary search to find the maximum valid minimum force. The basic idea is to check if it is possible to place all the balls with at least a certain minimum distance (force) between any two of them. If it is possible, try for a larger minimum distance, otherwise try smaller.

This C solution implements a binary search method to find the maximum minimum force. We first sort the basket positions, then binary search for the largest possible minimum distance using a helper function `canPlaceBalls` which checks if we can place all balls with at least `minDist` distance apart.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets.
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Greedy with Binary Search

This approach involves using a binary search for determining the optimal force, aided by a greedy strategy to verify if a particular minimum force is attainable. By iterating over the sorted positions, balls are placed as far apart as possible greedily. 

This C approach employs a binary search over potential forces while utilizing a greedy method to check if balls can be spaced with at least the current middle value as the force. The `canPlaceBalls` function iterates to find feasible placement for balls.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets.
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Binary Search

We notice that the greater the minimum magnetic force between any two balls, the fewer balls can be placed, which exhibits monotonicity. We can use binary search to find the maximum minimum magnetic force that allows the number of balls not less than m to be placed.

First, we sort the positions of the baskets, and then use binary search with the left boundary l = 1 and the right boundary r = position[n - 1], where n is the number of baskets. In each binary search iteration, we calculate the midpoint m = (l + r + 1) / 2, and then determine if there is a way to place the balls such that the number of balls placed is not less than m.

The problem is transformed into determining whether a given minimum magnetic force f can place m balls. We can traverse the positions of the baskets from left to right, and if the distance between the position of the last ball and the current basket's position is greater than or equal to f, it indicates that a ball can be placed in the current basket. Finally, we check if the number of balls placed is not less than m.

The time complexity is O(n times log n + n times log M), and the space complexity is O(log n). Here, n and M respectively represent the number of baskets and the maximum value of the basket positions.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Answer

Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets.
Space Complexity: O(1)

Greedy with Binary Search

Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets.
Space Complexity: O(1)

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on AnswerO(n log n + n log D)O(1)General optimal approach when maximizing a minimum distance or value
Greedy Placement with Binary SearchO(n log n)O(1)Best when the feasibility check can be verified greedily after sorting

Video Solution

Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIK • codestorywithMIK • 14,880 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Magnetic Force Between Two Balls easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing the binary search on answer pattern rather than brute forcing placements. Once that insight is clear, the implementation is straightforward.
Magnetic Force Between Two Balls Python/Java solution
Implementations in Python or Java follow the same structure: sort the positions array, binary search the distance range, and use a greedy loop to count how many balls can be placed for each candidate distance. If the count reaches m, increase the search range; otherwise decrease it.
How to solve Magnetic Force Between Two Balls in O(n)?
A pure O(n) solution is not practical because the positions must be sorted to evaluate valid spacing. The typical approach sorts the array first and then uses binary search with a linear greedy check. The resulting complexity is O(n log n).
What is the best approach for Magnetic Force Between Two Balls?
The most efficient approach is binary search on the answer combined with a greedy placement check. After sorting the basket positions, binary search the minimum distance between balls and verify feasibility by greedily placing balls with at least that gap. This runs in O(n log n + n log D) time and O(1) space.
Is Magnetic Force Between Two Balls asked at Google/Amazon/Meta?
This problem pattern frequently appears in interviews at companies like Amazon, Google, and Meta. It tests the "binary search on answer" technique, which is common in optimization problems involving distances, capacities, or minimum/maximum thresholds.
What data structure is used in Magnetic Force Between Two Balls?
The solution mainly uses a sorted array. The algorithm relies on binary search over the distance range and a greedy linear scan of the array to check if m balls can be placed with the required spacing.
What is the time complexity of Magnetic Force Between Two Balls?
The optimal solution runs in O(n log n + n log D) time. Sorting the positions costs O(n log n), and binary search over the distance range performs O(log D) checks, each scanning the array in O(n). Space complexity is O(1) beyond the input array.

Ready to solve this problem?

Practice Magnetic Force Between Two Balls with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimized Maximum of Products Distributed to Any Store