Show problems as
Classic problem #475MediumArrayTwo PointersBinary SearchSorting

Heaters

Real-world version: Smallest Mast Reach
Tracked in this browser only
Read Heaters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pipeline runs dead straight. sensors gives the positions of the sensor nodes bolted along it and masts gives the positions of the relay masts. Positions are whole numbers of metres, they arrive in no particular order, and two entries may share a position.

Every mast is configured with the same reach r. A mast at position p then covers the stretch from p - r to p + r, endpoints included, and a sensor counts as covered when at least one mast reaches it.

Return the smallest reach r that leaves every sensor covered.

Examples

Example 1

Input
sensors = [7,2,9], masts = [5]
Output
4

The single mast sits at 5, so the three sensors are 2, 3 and 4 metres away. A reach of 4 covers all three.

Example 2

Input
sensors = [12,3,8], masts = [10,1]
Output
2

The sensor at 3 is 2 metres from the mast at 1, the sensor at 8 is 2 metres from the mast at 10, and the sensor at 12 is also 2 metres from the mast at 10.

Example 3

Input
sensors = [9], masts = [2,100]
Output
7

The sensor at 9 is 7 metres from the mast at 2 and 91 metres from the mast at 100, so a reach of 7 covers it.

Example 4

Input
sensors = [5,5,5], masts = [5,9]
Output
0

Every sensor shares a position with a mast, so no reach at all is needed.

Constraints

  • 1 <= sensors.length, masts.length <= 3 * 10^4
  • 1 <= sensors[i], masts[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_radius(sensors: list[int], masts: list[int]) -> int:
Java
public int findRadius(int[] sensors, int[] masts)

More on the same topics