In the Magnetic Force Between Two Balls problem, you are given an integer array position representing the physical locations of various empty baskets on a number line. You are also given an integer m representing the number of magnetic balls you possess. You must place all m balls into the baskets. Because the balls are highly magnetic, they repel each other. Your goal is to place the balls in such a way that the minimum magnetic force (the physical distance) between any two adjacent balls is maximized. Return this maximized minimum distance.
Example 1
Input: position = [1, 2, 3, 4, 7], m = 3
Output: 3
Explanation: We have 3 balls to place. If we place them at baskets 1, 4, and 7, the distances between adjacent balls are 3 (between 1 and 4) and 3 (between 4 and 7). The minimum distance is 3. This is the absolute best separation we can achieve.
Example 2
Input: position = [5, 4, 3, 2, 1, 1000000000], m = 2
Output: 999999999
Explanation: We only have 2 balls. To maximize the distance between them, we place the first ball in the basket at position 1 and the second ball in the basket at position 1000000000. The distance between them is 999999999.
Brute Force Approach
We want to spread the items out as much as possible, which means maximizing the minimum distance between any two placed items. You can start by testing the smallest possible distance limit, such as a distance of 1. You iterate through the available positions, placing an item every time you find a position that is at least that distance away from the last placed item. If you successfully place all your items, you know a distance of 1 works. Then you try a distance limit of 2, then 3, testing sequentially until you reach a distance limit where you run out of valid positions before you can place all your items. The maximum successful distance you found right before this point is your answer.
Algorithm
Sort the
positionarray. The baskets must be in order from left to right so we can correctly measure distances.Determine the minimum possible answer, which is 1 (the smallest possible gap between two distinct integers).
Determine the maximum possible answer, which is the difference between the very last basket and the very first basket in our sorted array.
Run a loop starting from 1 up to the maximum possible answer to test every single distance limit.
For each distance, use a helper function to simulate placing the balls. Place the first ball in the first basket. Then, walk through the array. Whenever you find a basket that is at least the test distance away from your last placed ball, place a new ball there.
If you can place all
mballs with the current distance, it means this distance works.The loop continues until a distance fails. The very last successful distance is our maximum possible minimum force.
Dry Run
Magnetic Force Between 2 Balls Brute Dry Run
Solution
// C++ program to implement Magnetic Force Between Two Balls#include <bits/stdc++.h>using namespace std;class Solution {public: /* Helper function to verify if we can successfully place all m balls with a strict minimum distance between them */ bool canPlaceBalls(vector<int>& position, int m, int dist) { // Always place the first ball in the very first basket int ballsPlaced = 1; // Keep track of the exact coordinate where the last ball was placed int lastPlacedCoord = position[0]; // Walk through the remaining baskets to place the rest of the balls for (int i = 1; i < position.size(); i++) { // Check if the current basket is far enough from the last placed ball if (position[i] - lastPlacedCoord >= dist) { // The gap is valid, so place a new ball here ballsPlaced++; // Update the coordinate of the last placed ball lastPlacedCoord = position[i]; } // If we have successfully placed all required balls, return true if (ballsPlaced >= m) { return true; } } // We ran out of baskets before placing all balls return false; } /* Main function that checks all possible distances linearly starting from 1 up to the maximum physical spread */ int maxDistance(vector<int>& position, int m) { // Sorting is strictly required to process positions linearly sort(position.begin(), position.end()); // The smallest possible gap between two baskets int low = 1; // The absolute largest gap between the extreme ends of the array int high = position.back() - position[0]; // Variable to track the best valid distance found int result = 1; // Linearly test every single distance from low to high for (int dist = low; dist <= high; dist++) { // If the current distance allows all balls to be placed if (canPlaceBalls(position, m, dist)) { // Record this successful distance result = dist; } else { // The moment a distance fails, stop testing larger ones break; } } // Return the highest recorded valid distance return result; }};// Driver code starts hereint main() { // Instantiate the Solution class Solution obj; // Define the test basket positions vector<int> position = {1, 2, 3, 4, 7}; // Define the number of magnetic balls int m = 3; // Call the function and get the result int ans = obj.maxDistance(position, m); // Output the answer cout << ans << endl; return 0;}Complexity Analysis
Time Complexity: O((N x log2 N) + ((Max - Min) x N)), where N is the length of the array, Max is the largest element, and Min is the smallest element. Sorting takes N x log2 N. The outer loop tests up to (Max - Min) values, and for each value, we run a full array traversal of size N.
Space Complexity: O(1), as we only track counts and previous coordinates using basic primitive numbers, using strictly constant extra memory.
Optimal Approach
The linear search works correctly, but it is extremely slow. The physical coordinates of the baskets can go up to 1,000,000,000. Testing every single integer distance one by one up to a billion will cause a Time Limit Exceeded error.
The important pattern is how the chosen distance limit affects the ability to place all items. If the distance limit is small, it is much easier to find valid positions to place all the items, making it highly likely to work. If the distance limit is large, the items are forced too far apart, and we will run out of valid positions before placing all of them, which causes it to fail.
So, the possible distance limits form a monotonic pattern like this: possible, possible, possible, not possible, not possible, not possible.
The task is to find the last possible value, meaning the maximum possible distance where we can still successfully place all the items.
Binary search fits perfectly here because the results follow a strictly ordered pattern. Every successful distance tells us that all smaller distances will definitely work, but a larger (better) answer might still exist on the right. Conversely, every failed distance tells us that all larger distances will definitely fail, meaning we must shift our search space to the left. By repeatedly halving our search range, we can rapidly pinpoint the exact maximum valid distance without testing every number.
Algorithm
Sort the
positionarray to establish a left-to-right order.Initialize the lower bound to 1 and the upper bound to the total distance between the first and last basket.
Start a binary search loop. Find the middle distance between your lower and upper bounds.
Pass this middle distance to the helper function to see if all
mballs can be placed with at leastmiddledistance between them.If the placement is successful, it means this distance works. We save it as a potential answer. Since we want to maximize the distance, we move the lower bound up to check if an even larger distance works.
If the placement fails, it means the distance is too large. We move the upper bound down to test smaller distances.
Repeat the splitting process until the lower bound crosses the upper bound.
Dry Run
Magnetic Force Between 2 Balls Optimal Dry Run
Solution
// C++ program to implement Magnetic Force Between Two Balls#include <bits/stdc++.h>using namespace std;class Solution {public: /* Helper function to verify if we can successfully place all m balls with a strict minimum distance between them */ bool canPlaceBalls(vector<int>& position, int m, int dist) { // Always place the first ball in the very first basket int ballsPlaced = 1; // Keep track of the exact coordinate where the last ball was placed int lastPlacedCoord = position[0]; // Walk through the remaining baskets to place the rest of the balls for (int i = 1; i < position.size(); i++) { // Check if the current basket is far enough from the last placed ball if (position[i] - lastPlacedCoord >= dist) { // The gap is valid, so place a new ball here ballsPlaced++; // Update the coordinate of the last placed ball lastPlacedCoord = position[i]; } // If we have successfully placed all required balls, return true if (ballsPlaced >= m) { return true; } } // We ran out of baskets before placing all balls return false; } /* Optimal binary search approach to eliminate half of the potential distance limits with each iteration */ int maxDistance(vector<int>& position, int m) { // Sorting is strictly required to process positions linearly sort(position.begin(), position.end()); // The lowest possible optimal gap int low = 1; // The highest possible gap spanning the entire array width int high = position.back() - position[0]; // Variable to hold the maximum valid distance found so far int result = 1; // Execute binary search until the search space is exhausted while (low <= high) { // Calculate the middle distance guess to test int mid = low + (high - low) / 2; // If the balls can be successfully spread out by this mid distance if (canPlaceBalls(position, m, mid)) { // Record this as a valid answer result = mid; // Move the lower bound up to hunt for an even larger distance low = mid + 1; } else { // The distance is too strict, shift the upper bound down high = mid - 1; } } // Return the absolute optimal result found return result; }};// Driver code starts hereint main() { // Instantiate the Solution class Solution obj; // Define the test basket positions vector<int> position = {1, 2, 3, 4, 7}; // Define the number of magnetic balls int m = 3; // Call the optimal binary search function int ans = obj.maxDistance(position, m); // Print the final result to the console cout << ans << endl; return 0;}Complexity Analysis
Time Complexity: O(N log2 N + N * log2(Max - Min)), where N is the length of the position array. We sort the array first taking N log N time. The binary search operates over a range of (Max - Min) which takes logarithmic steps. In each step, we iterate over the array of size N.
Space Complexity: O(1), no separate structural arrays or complex variables are needed, ensuring the data footprint remains strictly minimal.
Interview follow-up Questions
The initial input array simply lists the basket coordinates in a random order. Our logic measures physical distance sequentially by jumping from the left side to the right side. If the array is not sorted, our program will jump randomly back and forth across the physical space, destroying the distance measurement completely.
Be the first to add a comment.