Problem statement

https://binarysearch.com/problems/Minimum-Light-Radius/

Solution

For each r we can check if it is enough to use 3 lights. We can use greedy strategy with again binary search inside: start from left and do 3 steps.

Complexity

It is O(n log n + 3 * log n * log M) for time and O(n) for space. Where n = len(A) and M = max(A) - min(A) + 1`.

Code

class Solution:
    def solve(self, A):
        A = sorted(A)
        def check(r):
            place = A[0]
            for i in range(3):
                idx = bisect.bisect(A, place + 2*r)
                if idx >= len(A): return True
                place = A[idx]
            return False

        beg, end = 0, max(A) - min(A) + 1
        while end - beg > 0.000001:
            mid = (beg + end)/2
            if check(mid):
                end = mid
            else:
                beg = mid

        return mid