Magnetic Force Between Two Balls solution and explanation
Google
9 more videos on this problem
Magnetic Force Between Two Balls | Simple Thought Process | Leetcode 1552 | codestorywithMIKcodestorywithMIK · 25:02 · 14K views
1552. Magnetic Force Between Two Balls | Binary Search on Answer | GreedyAryan Mittal · 15:13 · 10K views
1552. Magnetic Force Between Two Balls (Leetcode Medium)Programming Live with Larry · 7:36 · 4K views
1552. Magnetic Force Between Two Balls | binary search | leetcode daily challenge | DSA | HindiShashCode · 21:00 · 3K views
✅Magnetic Force Between Two Balls - LeetCode 1552 - Binary Search - Explained In DetailLeet Logics · 6:49 · 3K views
Magnetic Force Between Two Balls | Leetcode 1552Ayushi Sharma · 18:00 · 3K views
LeetCode 1552. Magnetic Force Between Two Balls (Python)AH Tech · 8:11 · 2K views
LeetCode 1552. Magnetic Force Between Two BallsHappy Coding · 23:25 · 2K views
1552. Magnetic Force Between Two Balls | Leetcode Daily Challenge (POTD) 20/06/2024 | Binary SearchAlgorithmHQ · 13:21 · 2K views
Magnetic Force Between Two Balls | Binary Search on Answer Pattern | (Java, C++, Python)RisingBrain · 20:29 · 1K views
The problem
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.length2 <= n <= 1051 <= position[i] <= 109- All integers in
positionare 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.
def can_place_balls(position, m, min_dist):
count = 1
last_position = position[0]
for i in range(1, len(position)):
if position[i] - last_position >= min_dist:
count += 1
last_position = position[i]
if count >= m:
return True
return False
def max_distance(position, m):
position.sort()
left, right = 1, position[-1] - position[0]
answer = 0
while left <= right:
mid = (left + right) // 2
if can_place_balls(position, m, mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
position = [1, 2, 3, 4, 7]
m = 3
print(max_distance(position, m))import java.util.Arrays;
class Solution {
public boolean canPlaceBalls(int[] position, int m, int minDist) {
int count = 1, lastPosition = position[0];
for (int i = 1; i < position.length; i++) {
if (position[i] - lastPosition >= minDist) {
count++;
lastPosition = position[i];
if (count >= m) {
return true;
}
}
}
return false;
}
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int left = 1, right = position[position.length - 1] - position[0];
int answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canPlaceBalls(position, m, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] position = {1, 2, 3, 4, 7};
int m = 3;
System.out.println(sol.maxDistance(position, m));
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool canPlaceBalls(const std::vector<int>& position, int m, int minDist) {
int count = 1, lastPosition = position[0];
for (int i = 1; i < position.size(); i++) {
if (position[i] - lastPosition >= minDist) {
count++;
lastPosition = position[i];
if (count >= m)
return true;
}
}
return false;
}
int maxDistance(std::vector<int>& position, int m) {
std::sort(position.begin(), position.end());
int left = 1, right = position.back() - position.front();
int answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canPlaceBalls(position, m, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
int main() {
std::vector<int> position = {1, 2, 3, 4, 7};
int m = 3;
std::cout << maxDistance(position, m) << std::endl;
return 0;
}function canPlaceBalls(position, m, minDist) {
let count = 1, lastPosition = position[0];
for (let i = 1; i < position.length; i++) {
if (position[i] - lastPosition >= minDist) {
count++;
lastPosition = position[i];
if (count >= m) {
return true;
}
}
}
return false;
}
function maxDistance(position, m) {
position.sort((a, b) => a - b);
let left = 1, right = position[position.length - 1] - position[0];
let answer = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (canPlaceBalls(position, m, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
const position = [1, 2, 3, 4, 7];
const m = 3;
console.log(maxDistance(position, m));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int canPlaceBalls(int *position, int n, int m, int minDist) {
int count = 1, lastPosition = position[0];
for (int i = 1; i < n; i++) {
if (position[i] - lastPosition >= minDist) {
count++;
lastPosition = position[i];
if (count >= m)
return 1;
}
}
return 0;
}
int maxDistance(int* position, int n, int m) {
qsort(position, n, sizeof(int), compare);
int left = 1, right = position[n - 1] - position[0];
int answer = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (canPlaceBalls(position, n, m, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
int main() {
int position[] = {1, 2, 3, 4, 7};
int n = 5;
int m = 3;
printf("%d\n", maxDistance(position, n, m));
return 0;
}using System;
class Solution {
public bool CanPlaceBalls(int[] position, int m, int minDist) {
int count = 1, lastPosition = position[0];
for (int i = 1; i < position.Length; i++) {
if (position[i] - lastPosition >= minDist) {
count++;
lastPosition = position[i];
if (count >= m) {
return true;
}
}
}
return false;
}
public int MaxDistance(int[] position, int m) {
Array.Sort(position);
int left = 1, right = position[position.Length - 1] - position[0];
int answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanPlaceBalls(position, m, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
static void Main() {
Solution sol = new Solution();
int[] position = {1, 2, 3, 4, 7};
int m = 3;
Console.WriteLine(sol.MaxDistance(position, m));
}
}In the Python solution, the positions are sorted first. Then a binary search determines the maximum minimum distance possible. The `can_place_balls` function checks if it’s feasible to place the balls such that all of them are at least `min_dist` apart, supporting the binary search process.
Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets.
Space Complexity: O(1)
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.
def can_place_balls(position, m, dist):
count, last_position = 1, position[0]
for i in range(1, len(position)):
if position[i] - last_position >= dist:
count += 1
last_position = position[i]
if count == m:
return True
return False
def max_distance(position, m):
position.sort()
left, right = 1, position[-1] - position[0]
while left < right:
mid = left + (right - left + 1) // 2
if can_place_balls(position, m, mid):
left = mid
else:
right = mid - 1
return left
position = [5, 4, 3, 2, 1, 1000000000]
m = 2
print(max_distance(position, m))import java.util.Arrays;
class Solution {
public boolean canPlaceBalls(int[] position, int m, int dist) {
int count = 1, last_position = position[0];
for (int i = 1; i < position.length; ++i) {
if (position[i] - last_position >= dist) {
count++;
last_position = position[i];
if (count == m) {
return true;
}
}
}
return false;
}
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int left = 1, right = position[position.length - 1] - position[0];
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canPlaceBalls(position, m, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] position = {5, 4, 3, 2, 1, 1000000000};
int m = 2;
System.out.println(sol.maxDistance(position, m));
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool canPlaceBalls(const std::vector<int>& position, int m, int dist) {
int count = 1, last_position = position[0];
for (size_t i = 1; i < position.size(); ++i) {
if (position[i] - last_position >= dist) {
count++;
last_position = position[i];
if (count == m) {
return true;
}
}
}
return false;
}
int maxDistance(std::vector<int>& position, int m) {
std::sort(position.begin(), position.end());
int left = 1, right = position.back() - position.front();
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canPlaceBalls(position, m, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
std::vector<int> position = {5, 4, 3, 2, 1, 1000000000};
int m = 2;
std::cout << maxDistance(position, m) << std::endl;
return 0;
}function canPlaceBalls(position, m, dist) {
let count = 1, lastPosition = position[0];
for (let i = 1; i < position.length; i++) {
if (position[i] - lastPosition >= dist) {
count++;
lastPosition = position[i];
if (count === m) {
return true;
}
}
}
return false;
}
function maxDistance(position, m) {
position.sort((a, b) => a - b);
let left = 1, right = position[position.length - 1] - position[0];
while (left < right) {
let mid = Math.floor(left + (right - left + 1) / 2);
if (canPlaceBalls(position, m, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
const position = [5, 4, 3, 2, 1, 1000000000];
const m = 2;
console.log(maxDistance(position, m));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int canPlaceBalls(int *position, int n, int m, int dist) {
int count = 1, last_position = position[0];
for (int i = 1; i < n; ++i) {
if (position[i] - last_position >= dist) {
count++;
last_position = position[i];
if (count == m) return 1;
}
}
return 0;
}
int maxDistance(int* position, int n, int m) {
qsort(position, n, sizeof(int), compare);
int left = 1, right = position[n - 1] - position[0];
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canPlaceBalls(position, n, m, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
int position[] = {5, 4, 3, 2, 1, 1000000000};
int n = 6;
int m = 2;
printf("%d\n", maxDistance(position, n, m));
return 0;
}using System;
class Solution {
public bool CanPlaceBalls(int[] position, int m, int dist) {
int count = 1, last_position = position[0];
for (int i = 1; i < position.Length; ++i) {
if (position[i] - last_position >= dist) {
count++;
last_position = position[i];
if (count == m) {
return true;
}
}
}
return false;
}
public int MaxDistance(int[] position, int m) {
Array.Sort(position);
int left = 1, right = position[position.Length - 1] - position[0];
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (CanPlaceBalls(position, m, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
static void Main() {
Solution sol = new Solution();
int[] position = {5, 4, 3, 2, 1, 1000000000};
int m = 2;
Console.WriteLine(sol.MaxDistance(position, m));
}
}This Python script comprises a binary search strategy to fine-tune the maximum minimum force. It cats through possible forces using `can_place_balls`, ensuring that the force is achievable.
Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets.
Space Complexity: O(1)
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.
function maxDistance(position: number[], m: number): number {
position.sort((a, b) => a - b);
let [l, r] = [1, position.at(-1)!];
const count = (f: number): number => {
let cnt = 1;
let prev = position[0];
for (const curr of position) {
if (curr - prev >= f) {
cnt++;
prev = curr;
}
}
return cnt;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (count(mid) >= m) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maxDistance(position []int, m int) int {
sort.Ints(position)
return sort.Search(position[len(position)-1], func(f int) bool {
prev := position[0]
cnt := 1
for _, curr := range position {
if curr-prev >= f {
cnt++
prev = curr
}
}
return cnt < m
}) - 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Answer | Time Complexity: O(n log(n) + log(maxDistance) * n), where n is the number of baskets. |
| Greedy with Binary Search | Time Complexity: O(n log(n) + n log(maxDistance)), where n is the number of baskets. |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Answer | O(n log n + n log D) | O(1) | General optimal approach when maximizing a minimum distance or value |
| Greedy Placement with Binary Search | O(n log n) | O(1) | Best when the feasibility check can be verified greedily after sorting |
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.