1552. Magnetic Force Between Two Balls

T: O(nlogn)
S: O(1)

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1;
        int right = position[position.length-1]; // the range should be 1 to last position (key is start from 1, because 1 still a posiible force!)
        // but for 1482. Minimum Number of Days to Make m Bouquets -> possible range is between min and max
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (inBasket(position, m, mid)) {
                if (mid+1 <= position[position.length-1] && inBasket(position, m, mid+1)) {
                    left = mid+1;
                } else {
                    return mid;
                }
                
            } else {
                right = mid-1;
            }
        }
        return -1;
    }
    /**
        greedy thought
        always use first basket as the first position of the ball
        then try to find new j -> position[j] - position[i] == force
        if can't find..then j would be reach the end
        or find -> j can be the new start (has ball), then find next position[j] - position[i] == force
     */
    private boolean inBasket(int[] position, int m, int force) {

        int count = 1;
        for (int i = 0; i < position.length;) {
            int j = i;
            while (j < position.length && position[j] - position[i] < force) {
                j++;
            }
            if (j == position.length) { // force is too big, can't find the next basket for ball
                break;
            } else {
                count++;
                i = j;
            }
            if (m == count) {
                return true;
            }
        }
        return false;
    }
}

/**
Greedy + BS

minimum magnetic force between any two balls is maximum.
magnetic force: |x - y|


2 4 6

3 3 6


T: O(nlogn)
S: O(1)
 */