1552. Magnetic Force Between Two Balls

The daily leetcode problem for June 20th 2024.

Intuition

The problem asks to maximize the minimum magnetic force between two balls. For this type of problem, it's easy to check if x magnetic force can be achieved, simply sort the positions array in ascending order and check if you could place m balls separated by at least x.

However, how do you find the maximum this minimum x can be? Binary search! For all problems that say maximize a minimum or minimize a maximum binary search should be considered as an option. In this case if a large x doesn’t work even larger x won’t work, so it's possible to eliminate the possibilities from the search space with an easy binary search.

Approach

• Sort the positions, these don’t come sorted.
• Write a binary search loop to find the maximum minimum distance of balls, use a helper function to check is x can be achieved for m balls and eliminate possibilities in the search space accordingly.

Code

const canMake = (position, m, target)=>{
    let prev = position[0];
    m--;
    for(let i = 1; i < position.length && m > 0; i++){
        if(Math.abs(prev -  position[i]) >= target){
            prev = position[i];
            m--;
        }
    }
    return m==0;
}

const maxDistance = (position, m) => {
    let minim = 1, maxim = 1e9;
    position.sort((a,b)=> a-b);
    while(minim != maxim){
        let mid = Math.ceil((minim + maxim) / 2);
        const canAchieve = canMake(position, m, mid);
        if(canAchieve) {
            minim = mid;
        } else {
            maxim = mid - 1;
        }
    }
    return minim;
};

Complexity

Time: O(nlogn + min(n,m) * log(1e9))
Space: O(n)

Assuming sort is mergesort.