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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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

1
2
3
4
5

Input: listeners = [1], towers = [1]
Output: 0
Explanation: 
- Listener is at the same position as the tower
- No broadcast range needed.

Example 5

1
2
3
4
5
6
7

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

  1. For each listener position, find the closest tower by checking distance to all towers
  2. Calculate the minimum distance from the listener to any tower
  3. Keep track of the maximum of all these minimum distances
  4. Return this maximum distance as the minimum broadcast range needed

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

  1. Sort the towers array for binary search
  2. For each listener, use binary search to find the position where the listener would be inserted
  3. Check the tower just before and just after this position to find the closest one
  4. Calculate the distance to the closest tower
  5. Keep track of the maximum distance across all listeners

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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)