Magnetic Force Between Two Balls

Med

#1429Time: O(n log n + D * n), where `D` is the maximum distance (`position[n-1] - position[0]`). Sorting takes `O(n log n)`. The loop runs up to `D` times, and each call to `canPlace` takes `O(n)`. Since `D` can be up to `10^9`, this approach is too slow.Space: O(log n) or O(n) for sorting, depending on the implementation. If sorting is done in-place, the space complexity is O(log n) for the recursion stack or O(1) for iterative sorts like Heapsort.2 companies

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Roblox PhonePe

Prompt

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 i^th 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 <= 10⁵
1 <= position[i] <= 10⁹
All integers in position are distinct.
2 <= m <= position.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible value for the minimum distance, from the largest possible down to the smallest. The first distance that allows placing m balls is the maximum possible minimum distance. While conceptually simple, it is too slow for the given constraints.

Algorithm

Sort the position array in ascending order.
The maximum possible value for the minimum distance is D = position[n-1] - position[0]. The minimum is 1.
We can iterate through all possible integer distances d from D down to 1.
For each d, we check if it's possible to place m balls with at least d distance between them using a greedy helper function canPlace(d).
The canPlace(d) function works as follows:
1. Place the first ball at position[0].
2. Iterate through the remaining positions, placing the next ball at the earliest possible spot position[i] that maintains the minimum distance d from the previously placed ball.
3. Count the total number of balls placed. If it's at least m, canPlace(d) returns true.
The first (and largest) d for which canPlace(d) returns true is the answer.

Walkthrough

The core idea is to transform the problem from finding a specific arrangement of balls to finding an optimal value for the minimum distance. We can test each possible distance value to see if it's feasible.

First, we sort the position array. This allows us to greedily check for placements. The possible values for the minimum distance d are in the range [1, position[n-1] - position[0]].

We can iterate d from the maximum possible value downwards. For each d, we check if we can place m balls. To do this, we use a greedy function canPlace(d):

Place the first ball at position[0].
Iterate from position[1] onwards. Find the next basket position[i] such that its distance from the last placed ball is at least d.
Place a ball there and repeat until we have either placed m balls or run out of baskets.

If we can place m balls, we have found our answer because we are iterating from the largest d downwards. If not, we try a smaller d.

1import java.util.Arrays;2 3class Solution {4    public int maxDistance(int[] position, int m) {5        Arrays.sort(position);6        int n = position.length;7        int maxPossibleDist = position[n - 1] - position[0];8 9        for (int d = maxPossibleDist; d >= 1; d--) {10            if (canPlace(position, m, d)) {11                return d;12            }13        }14        return 0; // Should not be reached given the constraints15    }16 17    // Checks if we can place m balls with at least d distance apart.18    private boolean canPlace(int[] position, int m, int d) {19        int ballsPlaced = 1;20        int lastPosition = position[0];21        for (int i = 1; i < position.length; i++) {22            if (position[i] - lastPosition >= d) {23                ballsPlaced++;24                lastPosition = position[i];25            }26        }27        return ballsPlaced >= m;28    }29}

Complexity

Time

O(n log n + D * n), where `D` is the maximum distance (`position[n-1] - position[0]`). Sorting takes `O(n log n)`. The loop runs up to `D` times, and each call to `canPlace` takes `O(n)`. Since `D` can be up to `10^9`, this approach is too slow.

Space

O(log n) or O(n) for sorting, depending on the implementation. If sorting is done in-place, the space complexity is O(log n) for the recursion stack or O(1) for iterative sorts like Heapsort.

Trade-offs

Pros

Conceptually simpler to understand than binary search.
Correctly identifies the problem as a search for the optimal distance.

Cons

Extremely inefficient due to the large search space for the distance d.
Will result in a 'Time Limit Exceeded' error for most competitive programming platforms due to the constraints.

This approach optimizes the search for the maximum possible minimum distance by using binary search. Instead of checking every possible distance, we efficiently narrow down the search space. This is a classic technique for problems that ask to 'maximize a minimum' or 'minimize a maximum'.

Algorithm

First, sort the position array in ascending order.
The problem has a monotonic property: if a distance d is achievable, any distance d' < d is also achievable. This allows us to use binary search on the answer.
Define a search space for the answer d. The lower bound low is 1, and the upper bound high is position[n-1] - position[0].
While low <= high:
- Calculate the middle value mid = low + (high - low) / 2.
- Use a greedy helper function canPlace(mid) to check if it's possible to place m balls with a minimum distance of at least mid.
- If canPlace(mid) is true, it means mid is a possible answer. We try for a larger distance, so we store mid as a potential answer and set low = mid + 1.
- If canPlace(mid) is false, mid is too large. We need to try a smaller distance, so we set high = mid - 1.
The last valid mid stored is the maximum possible minimum distance.

Walkthrough

The key insight is that the feasibility of a minimum distance d is monotonic. If we can place m balls with a minimum distance of d, we can certainly do so for any distance smaller than d. This allows us to binary search for the largest possible d that works.

The search range for our answer d will be from 1 to position[n-1] - position[0]. We'll call these bounds low and high.

In each step of the binary search, we take a candidate distance mid and check if it's possible to place m balls with at least this separation. This check is performed by a greedy helper function canPlace(d):

Place the first ball at position[0].
Iterate through the sorted positions and place the next ball at the first available basket that is at least d distance away from the last placed ball.
If we are able to place m or more balls, canPlace(d) returns true.

Based on the result of canPlace(mid):

If it's true, mid is a valid distance. We store it as our current best answer and try for an even larger distance by setting low = mid + 1.
If it's false, mid is too large. We need to try smaller distances, so we set high = mid - 1.

This process continues until low crosses high, and our stored answer will be the maximum possible minimum distance.

1import java.util.Arrays;2 3class Solution {4    public int maxDistance(int[] position, int m) {5        Arrays.sort(position);6        int n = position.length;7        int low = 1;8        int high = position[n - 1] - position[0];9        int ans = 0;10 11        while (low <= high) {12            int mid = low + (high - low) / 2;13            if (canPlace(position, m, mid)) {14                ans = mid; // This distance is possible, try for a larger one.15                low = mid + 1;16            } else {17                high = mid - 1; // This distance is not possible, try a smaller one.18            }19        }20        return ans;21    }22 23    // Checks if we can place m balls with at least d distance apart.24    private boolean canPlace(int[] position, int m, int d) {25        int ballsPlaced = 1;26        int lastPosition = position[0];27        for (int i = 1; i < position.length; i++) {28            if (position[i] - lastPosition >= d) {29                ballsPlaced++;30                lastPosition = position[i];31                if (ballsPlaced == m) {32                    return true;33                }34            }35        }36        return false;37    }38}

Complexity

Time

O(n log n + n log D), where `D` is the maximum distance (`position[n-1] - position[0]`). Sorting takes `O(n log n)`. The binary search runs `log D` times, and each call to `canPlace` takes `O(n)`. This is efficient enough to pass the given constraints.

Space

O(log n) or O(n) for sorting, depending on the implementation. If sorting is done in-place, the space complexity is O(log n) for the recursion stack or O(1) for iterative sorts like Heapsort.

Trade-offs

Pros

Highly efficient due to the logarithmic reduction of the search space.
Guaranteed to find the optimal solution.
A classic and powerful technique for 'maximize the minimum' or 'minimize the maximum' type problems.

Cons

Slightly more complex to understand and implement than a linear scan.
Requires identifying the monotonic property of the problem to apply binary search.

Solutions

Solution

1class Solution {2public3  int maxDistance(int[] position, int m) {4    Arrays.sort(position);5    int left = 1, right = position[position.length - 1];6    while (left < right) {7      int mid = (left + right + 1) >>> 1;8      if (check(position, mid, m)) {9        left = mid;10      } else {11        right = mid - 1;12      }13    }14    return left;15  }16private17  boolean check(int[] position, int f, int m) {18    int prev = position[0];19    int cnt = 1;20    for (int i = 1; i < position.length; ++i) {21      int curr = position[i];22      if (curr - prev >= f) {23        prev = curr;24        ++cnt;25      }26    }27    return cnt >= m;28  }29}

1/** * @param {number[]} position * @param {number} m * @return {number} */ var maxDistance =2  function (position, m) {3    position.sort((a, b) => {4      return a - b;5    });6    let left = 1,7      right = position[position.length - 1];8    const check = function (f) {9      let prev = position[0];10      let cnt = 1;11      for (let i = 1; i < position.length; ++i) {12        const curr = position[i];13        if (curr - prev >= f) {14          prev = curr;15          ++cnt;16        }17      }18      return cnt >= m;19    };20    while (left < right) {21      const mid = (left + right + 1) >> 1;22      if (check(mid)) {23        left = mid;24      } else {25        right = mid - 1;26      }27    }28    return left;29  };

1class Solution {2public:3  int maxDistance(vector<int> &position, int m) {4    sort(position.begin(), position.end());5    int left = 1, right = position[position.size() - 1];6    while (left < right) {7      int mid = (left + right + 1) >> 1;8      if (check(position, mid, m))9        left = mid;10      else11        right = mid - 1;12    }13    return left;14  }15  bool check(vector<int> &position, int f, int m) {16    int prev = position[0];17    int cnt = 1;18    for (int i = 1; i < position.size(); ++i) {19      int curr = position[i];20      if (curr - prev >= f) {21        prev = curr;22        ++cnt;23      }24    }25    return cnt >= m;26  }27};

1class Solution:2    def maxDistance(self, position: List[int], m: int) -> int: def check(f): prev = position[0] cnt = 1 for curr in position[1:]: if curr - prev >= f: prev = curr cnt += 1 return cnt >= m position . sort() left, right = 1, position[- 1] while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid - 1 return left

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem