You are given an array of network towers towers, where towers[i] = [xi, yi, qi] denotes the ith network tower with location (xi, yi) and quality factor qi. All the coordinates are integral coordinates on the X-Y plane, and the distance between the two coordinates is the Euclidean distance.
You are also given an integer radius where a tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.
The signal quality of the ith tower at a coordinate (x, y) is calculated with the formula ⌊qi / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.
Return the array [cx, cy] representing the integral coordinate (cx, cy) where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum non-negative coordinate.
Note:
(x1, y1) is lexicographically smaller than (x2, y2) if either:
x1 < x2, orx1 == x2 and y1 < y2.⌊val⌋ is the greatest integer less than or equal to val (the floor function).Example 1:
Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2 Output: [2,1] Explanation: At coordinate (2, 1) the total quality is 13. - Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7 - Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2 - Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4 No other coordinate has a higher network quality.
Example 2:
Input: towers = [[23,11,21]], radius = 9 Output: [23,11] Explanation: Since there is only one tower, the network quality is highest right at the tower's location.
Example 3:
Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2 Output: [1,2] Explanation: Coordinate (1, 2) has the highest network quality.
Constraints:
1 <= towers.length <= 50towers[i].length == 30 <= xi, yi, qi <= 501 <= radius <= 50The key idea in #1620 Coordinate With Maximum Network Quality is to evaluate how much signal each possible coordinate receives from nearby towers. Each tower contributes a signal strength based on floor(qi / (1 + distance)), but only if the Euclidean distance between the tower and the coordinate is less than or equal to the given radius.
Since tower coordinates are bounded (typically within 0–50), a practical strategy is enumeration. Iterate through all integer coordinates in the possible grid and compute the total signal received from every tower. For each coordinate, calculate the distance to each tower, check if it lies within the radius, and accumulate the valid signal contributions.
Track the coordinate with the maximum total signal. If multiple coordinates yield the same signal, choose the one with the smallest x, and if needed, the smallest y. This brute-force grid enumeration works efficiently due to the small coordinate bounds. The approach mainly relies on array traversal and mathematical distance calculations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Grid Enumeration with Tower Signal Calculation | O(G^2 * n) where G ≈ 50 | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The constraints are small enough to consider every possible coordinate and calculate its quality.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The coordinate limits are small, typically within a 51x51 grid. This means checking every coordinate and evaluating signals from each tower remains computationally manageable. The overall operations stay within practical limits even with multiple towers.
While the exact problem may not always appear, similar grid-search and signal aggregation problems are common in technical interviews. These questions test understanding of enumeration, geometry calculations, and careful implementation of constraints.
The problem mainly uses arrays to store tower information and simple variables to track the best coordinate. Since the grid size is small, complex data structures are unnecessary. Mathematical computations and iteration are the main tools used.
The common approach is to enumerate all possible integer coordinates within the grid bounds and compute the signal received from each tower. For every coordinate, calculate the distance to each tower and add the contribution if it is within the radius. The coordinate with the highest accumulated signal is chosen, with tie-breaking based on smaller x and y values.