LeetCode 1552: Magnetic Force Between Two Balls Solution

Master LeetCode problem 1552 (Magnetic Force Between Two Balls), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1552. Magnetic Force Between Two Balls

Medium

Array Binary Search Sorting

Problem Explanation

Explanation:

To solve this problem, we can use a binary search approach. The idea is to find the maximum minimum magnetic force between any two balls by trying different minimum magnetic forces using binary search.

First, we sort the positions of the baskets.
We initialize the left and right bounds for our binary search. The left bound is 1 (minimum possible magnetic force) and the right bound is the maximum possible magnetic force which is the distance between the first and last position in the sorted array.
In each iteration of the binary search, we calculate the mid value between left and right, which represents our current minimum magnetic force guess.
We then try to place the balls in such a way that the minimum magnetic force between any two balls is at least the mid value. If we can successfully place all the balls, we update our answer with the mid value and move our left bound to mid + 1.
If we cannot place all the balls with the current mid value, it means the force is too high, so we move our right bound to mid - 1.
We continue this process until left is greater than right, at which point we return the answer.

Solution Code

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1;
        int right = position[position.length - 1] - position[0];
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (isValid(position, m, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private boolean isValid(int[] position, int m, int minForce) {
        int count = 1;
        int prev = position[0];
        
        for (int i = 1; i < position.length; i++) {
            if (position[i] - prev >= minForce) {
                count++;
                prev = position[i];
            }
        }
        
        return count >= m;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1552 (Magnetic Force Between Two Balls)?

This page provides optimized solutions for LeetCode problem 1552 (Magnetic Force Between Two Balls) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1552 (Magnetic Force Between Two Balls)?

The time complexity for LeetCode 1552 (Magnetic Force Between Two Balls) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1552 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1552 in Java, C++, or Python.

Back to LeetCode Solutions