Radio Waves: Find All Pairs of Towers Within Communication Range

Question

## Problem You are given `n` radio towers on a 2D plane. Two towers can communicate if the Euclidean distance between them is at most `R`. Return the count of all pairs `(i, j)` with `i < j` that can communicate. ```python from typing import List def count_pairs(towers: List[List[float]], R: float) -> int: # towers: [[x, y], ...] # R: max communication range # return: number of communicating pairs pass ``` **Example:** ``` towers = [[0,0],[3,0],[0,4],[3,4]] R = 5.0 Distances: (0,0)-(3,0) = 3.0 <= 5 -> pair (0,0)-(0,4) = 4.0 <= 5 -> pair (0,0)-(3,4) = 5.0 <= 5 -> pair (3,0)-(0,4) = 5.0 <= 5 -> pair (3,0)-(3,4) = 4.0 <= 5 -> pair (0,4)-(3,4) = 3.0 <= 5 -> pair Output: 6 ``` ## Approach Brute force O(n^2) compares all pairs. Use `distance_squared <= R*R` to avoid `sqrt`. ## Follow-ups 1. How would you reduce complexity below O(n^2) for large `n` using a spatial index (k-d tree or grid bucketing)? 2. What if towers can boost their range dynamically — how do you handle asymmetric communication? 3. How would you find the connected components of towers that can relay messages to each other? 4. What if R changes frequently — what data structure supports range queries efficiently with updates?

Radio Waves: Find All Pairs of Towers Within Communication Range

Question Details

Full Details

Topics

More from Snowflake