All problems

Minimum Broadcast Radius

Medium · binary search

Houses stand along a straight road. You are given houses, where houses[i] is the position of the i-th house (a whole number, possibly negative). The list is not sorted and two houses can share a position.

You will build exactly k transmitters, each at any whole-number position you like, and every transmitter gets the same radius r. A transmitter at position p reaches every house whose position x satisfies |x - p| <= r. Several transmitters may stand at the same spot, and a house may be reached by more than one.

Return the smallest whole number r for which k transmitters can reach every house. If there is a transmitter for every house (or all houses share a position), the answer is 0.

Examples

Example 1

Input: houses = [1, 2, 3, 4, 5], k = 1

Output: 2

One transmitter at position 3 with radius 2 reaches positions 1 to 5. Radius 1 reaches only three positions.

Example 2

Input: houses = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 2

Output: 2

Transmitters at 3 and 8, each with radius 2, reach 1 to 5 and 6 to 10.

Example 3

Input: houses = [1, 10], k = 1

Output: 5

A single transmitter has to sit somewhere between the two houses. At 5 or 6 it must still reach the far house, 5 away.

Constraints

• 1 <= len(houses) <= 10^5
• -10^9 <= houses[i] <= 10^9
• 1 <= k <= len(houses)