Minimum Radio Tower Broadcast Range
MediumUpdated: Aug 10, 2025
Problem
You are the technical director of WSPT radio, serving listeners nationwide. For simplicity's sake we can consider each listener to live along a horizontal line stretching from 0 (west) to 1000 (east).
Given a list of N listeners, and a list of M radio towers, each placed at various locations along this line, determine what the minimum broadcast range would have to be in order for each listener's home to be covered.
For example, suppose listeners = [1, 5, 11, 20], and towers = [4, 8, 15]. In this case the minimum range would be 5, since that would be required for the tower at position 15 to reach the listener at position 20.
Examples
Example 1
Input: listeners = [1, 5, 11, 20], towers = [4, 8, 15]
Output: 5
Explanation:
- Listener at 1: closest tower at 4, distance = 3
- Listener at 5: closest tower at 4, distance = 1
- Listener at 11: closest tower at 8, distance = 3
- Listener at 20: closest tower at 15, distance = 5
Maximum distance is 5, so minimum range needed is 5.
Example 2
Input: listeners = [1, 2, 3, 4, 5], towers = [3]
Output: 2
Explanation:
- Single tower at position 3 must cover all listeners
- Farthest listeners are at positions 1 and 5
- Distance from tower to position 1 = 2, to position 5 = 2
- Minimum range needed is 2.
Example 3
Input: listeners = [10, 20, 30], towers = [15, 25]
Output: 5
Explanation:
- Listener at 10: closest tower at 15, distance = 5
- Listener at 20: closest tower at 15, distance = 5 (or tower at 25, distance = 5)
- Listener at 30: closest tower at 25, distance = 5
Maximum distance is 5.
Example 4
Input: listeners = [1], towers = [1]
Output: 0
Explanation:
- Listener is at the same position as the tower
- No broadcast range needed.
Example 5
Input: listeners = [1, 10, 100], towers = [5, 50, 95]
Output: 5
Explanation:
- Listener at 1: closest tower at 5, distance = 4
- Listener at 10: closest tower at 5, distance = 5
- Listener at 100: closest tower at 95, distance = 5
Maximum distance is 5.
Solution
Method 1 - Brute Force Distance Calculation
Intuition
For each listener, we need to find the closest radio tower and calculate the distance. The minimum broadcast range needed is the maximum of all these minimum distances. This ensures every listener can receive signal from at least one tower.
Approach
- For each listener position, find the closest tower by checking distance to all towers
- Calculate the minimum distance from the listener to any tower
- Keep track of the maximum of all these minimum distances
- Return this maximum distance as the minimum broadcast range needed
Code
C++
class Solution {
public:
int minBroadcastRange(vector<int>& listeners, vector<int>& towers) {
int maxDist = 0;
for (int listener : listeners) {
int minDist = INT_MAX;
for (int tower : towers) {
minDist = min(minDist, abs(listener - tower));
}
maxDist = max(maxDist, minDist);
}
return maxDist;
}
};
Go
func minBroadcastRange(listeners []int, towers []int) int {
maxDist := 0
for _, listener := range listeners {
minDist := math.MaxInt32
for _, tower := range towers {
dist := listener - tower
if dist < 0 {
dist = -dist
}
if dist < minDist {
minDist = dist
}
}
if minDist > maxDist {
maxDist = minDist
}
}
return maxDist
}
Java
class Solution {
public int minBroadcastRange(int[] listeners, int[] towers) {
int maxDist = 0;
for (int listener : listeners) {
int minDist = Integer.MAX_VALUE;
for (int tower : towers) {
minDist = Math.min(minDist, Math.abs(listener - tower));
}
maxDist = Math.max(maxDist, minDist);
}
return maxDist;
}
}
Python
class Solution:
def minBroadcastRange(self, listeners: List[int], towers: List[int]) -> int:
max_dist = 0
for listener in listeners:
min_dist = float('inf')
for tower in towers:
min_dist = min(min_dist, abs(listener - tower))
max_dist = max(max_dist, min_dist)
return max_dist
Complexity
- ⏰ Time complexity:
O(N × M), where N is number of listeners and M is number of towers, as we check all tower distances for each listener - 🧺 Space complexity:
O(1), only using constant extra space for variables
Method 2 - Binary Search with Sorted Arrays
Intuition
We can optimize the tower search by sorting the towers first and using binary search to find the closest tower to each listener. For any listener position, the closest tower is either the largest tower ≤ listener position or the smallest tower > listener position.
Approach
- Sort the towers array for binary search
- For each listener, use binary search to find the position where the listener would be inserted
- Check the tower just before and just after this position to find the closest one
- Calculate the distance to the closest tower
- Keep track of the maximum distance across all listeners
Code
C++
class Solution {
public:
int minBroadcastRangeOptimized(vector<int>& listeners, vector<int>& towers) {
sort(towers.begin(), towers.end());
int maxDist = 0;
for (int listener : listeners) {
int minDist = INT_MAX;
// Find closest tower using binary search
auto it = lower_bound(towers.begin(), towers.end(), listener);
// Check tower at or after listener position
if (it != towers.end()) {
minDist = min(minDist, abs(*it - listener));
}
// Check tower before listener position
if (it != towers.begin()) {
--it;
minDist = min(minDist, abs(*it - listener));
}
maxDist = max(maxDist, minDist);
}
return maxDist;
}
};
Go
import "sort"
func minBroadcastRangeOptimized(listeners []int, towers []int) int {
sort.Ints(towers)
maxDist := 0
for _, listener := range listeners {
minDist := math.MaxInt32
// Binary search for closest tower
idx := sort.SearchInts(towers, listener)
// Check tower at or after listener position
if idx < len(towers) {
dist := towers[idx] - listener
if dist < 0 {
dist = -dist
}
if dist < minDist {
minDist = dist
}
}
// Check tower before listener position
if idx > 0 {
dist := towers[idx-1] - listener
if dist < 0 {
dist = -dist
}
if dist < minDist {
minDist = dist
}
}
if minDist > maxDist {
maxDist = minDist
}
}
return maxDist
}
Java
class Solution {
public int minBroadcastRangeOptimized(int[] listeners, int[] towers) {
Arrays.sort(towers);
int maxDist = 0;
for (int listener : listeners) {
int minDist = Integer.MAX_VALUE;
// Binary search for closest tower
int idx = Arrays.binarySearch(towers, listener);
if (idx >= 0) {
// Exact match found
return Math.max(maxDist, 0);
} else {
// Convert negative index to insertion point
idx = -(idx + 1);
}
// Check tower at or after listener position
if (idx < towers.length) {
minDist = Math.min(minDist, Math.abs(towers[idx] - listener));
}
// Check tower before listener position
if (idx > 0) {
minDist = Math.min(minDist, Math.abs(towers[idx - 1] - listener));
}
maxDist = Math.max(maxDist, minDist);
}
return maxDist;
}
}
Python
class Solution:
def minBroadcastRangeOptimized(self, listeners: List[int], towers: List[int]) -> int:
towers.sort()
max_dist = 0
for listener in listeners:
min_dist = float('inf')
# Binary search for closest tower
import bisect
idx = bisect.bisect_left(towers, listener)
# Check tower at or after listener position
if idx < len(towers):
min_dist = min(min_dist, abs(towers[idx] - listener))
# Check tower before listener position
if idx > 0:
min_dist = min(min_dist, abs(towers[idx - 1] - listener))
max_dist = max(max_dist, min_dist)
return max_dist
Complexity
- ⏰ Time complexity:
O(M log M + N log M), where M log M for sorting towers and N log M for binary search for each listener - 🧺 Space complexity:
O(1), only using constant extra space (if we don't count the space for sorting)