unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1552: Magnetic Force Between Two Balls

link

We recast the problem of maximizing the minimum force into the problem: Given the sequence of minimum forces \langle 1, 2, 3, \ldots, k \rangle, what is the rightmost value that is achievable. To search the rightmost value, we perform binary search in the range [1, pos_{max} - pos_{min}]. In each iteration of the binary-search, we check, for a given value of minimum force, all m balls can be placed. To make that check efficient we also sort position.

Time: \mathcal{O}(n \cdot \lg{ (pos_{max} - pos_{min}) }), space: that of sorting.

class Solution:
    def can_place(self, position, m, min_force) -> bool:
        prev, curr = 0, 1
        m = m-1
        while curr < len(position) and m > 0:
            if abs( position[prev] - position[curr] ) < min_force:
                curr += 1
                continue

            m -= 1
            prev = curr
            curr += 1
            
        return m == 0
        
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        lo, hi = 1, position[-1] - position[0]
        force = 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.can_place(position, m, mid):
                force = mid
                lo = mid+1
            else:
                hi = mid-1
        return force

tanvirdotzaman

,

Leave a comment