1552.magnetic-force-between-two-balls.md

1552. Magnetic Force Between Two Balls

Binary Search

We will use distance to represent the force between the balls in the following note. And please note that the distance is not necessarily adjacent (positions could be [5, 88, 588, 5888], and we have to use position[i] to calculate the distance, rather than the index i itself.

Given two balls and sorted position, what's the minimum distance? That would be the minimum amoung the two adjacent pairs (just right to the next). And the maximum distance would be the distance between the leftmost and rightmost positions (a..f). If we have more balls, then the distance would definitely be in this range.

positions: a, _, _, d, _, _, _, e, _ f
           |-------------------------|  // The maximum distance
                                |----|  // The minimum distance

We have a fixed search space, next, we'd like to discover the monotonicity characteristic to apply binary search:

As the distance increases, the number of balls we can place decreases. (we have to put m balls)

• If we can place all the balls with a minimum distance d (other distances might be larger than d, it's acceptable), then we can also place all the balls with a shorter distance d2 where d2 < d. For example, we can put 3 balls with the distance 4, then we can also put 3 balls with the distance 3, 2, 1.

positions = 1, 2, 3, 4, 5, 6, 7, 8, 9
            A           B           C   // distance = `d`
            A        B        C         // distance = `d - 1`
            A     B     C               // distance = `d - 2`
            A  B  C                     // distance = `d - 3`

• If we can't place the balls with a distance d, then we can't place the balls with a larger distance d2 where d2 > d.

positions = 1, 2, 3, 4, 5, 6, 7, 8, 9
            A           B           C   // distance = `d`
            A        B        C         // distance = `d - 1`
            A     B     C               // distance = `d - 2`
            A  B  C                     // distance = `d - 3`

This establishes the monotonicity characteristic, we can apply binary search to find the answer. We're looking for the last element that satisfies the condition: "we can put m balls within that given distance".

// m = 5
distances   1  2  3  4  5  6  7  8
feasible    O, O, O, O, X, X, X  X
                     ^
                     Max distance

fun maxDistance(position: IntArray, m: Int): Int {
    position.sort()
    var min = Int.MAX_VALUE
    for (i in 1 until position.size) {
        min = minOf(min, position[i] - position[i - 1])
    }
    var left = min
    var right = position.last() - position.first()
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (canPlaceAll(position, m, middle)) left = middle + 1
        else right = middle - 1
    }
    return right
}

// Check if we can place all balls at a given distance?
private fun canPlaceAll(position: IntArray, totalBalls: Int, minDistance: Int): Boolean {
    // We've placed the first ball, so we have `totalBalls - 1` balls left
    var balls = totalBalls - 1 
    var prev = position[0]
    for (i in 1 until position.size) {
        if (position[i] - prev >= minDistance) {
            prev = position[i]
            balls--
        }
    }
    return balls <= 0
}