LeetCode 1552.

Question

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.

Intuition

From the description, we can know that the answer should be in the range : 0<=answer<=10^9-1 because 1<=x,y<=10^9.

On my first thought, I wanna use BS to get the answer because the answer is the specific range (meaning we can use BS)

Approach

According to my first thought, my solution should be like this:

1. sorting initial array (cuz BS requires sorted array)
2. getting a current value by BS
3. testing if the value is qualified
4. pointer moves left if the value is qualified; otherwise pointer moves right

The rest we need to figure out is: What is the definition of qualification? or How to judge if the value is qualified?.

Here is my answer: Use Greedy Algorithm. First we create a counter which equals m. Then we get the first element of sorted array and set it as previous element. Once the |current - previous| >= range(BS generated) we then set current value as previous element and the counter minus one. Until the counter turns to 0 (qualified) or the iteration is done (not qualified).

Complexity

• Time complexity: O(nlogn)

• Space complexity: O(1)

Code

import java.util.Arrays;

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position); //nlogn
        int left = 0, right = (position[position.length-1]-position[0]) / (m-1);
        while (left <= right) {//logn
            int mid = left + (right - left) / 2;
            if (!isQualified(position, m, mid)) {//n
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left - 1;
    }

    public boolean isQualified(int[] position, int m, int range) {
        m--; // always get the first element
        int prev = position[0];
        for (int i=0; i<position.length; i++) {
            if (position[i]-prev >= range) {
                if (--m == 0) { // counter turns to 0
                    return true;
                }
                prev = position[i];
            }
        }
        return false;
    }
}

Check out the description of these two problems at LC 1552.