Watch 4 video solutions for Coordinate With Maximum Network Quality, a medium level problem involving Array, Enumeration. This walkthrough by EasyLeetcode has 1,034 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 50Problem Overview: You receive a list of network towers where each tower has an (x, y) coordinate and a signal quality value. For any coordinate within the grid, you compute the network quality by summing contributions from towers within a given radius using the formula floor(q / (1 + distance)). The task is to return the coordinate that yields the maximum total signal quality. If multiple coordinates produce the same value, return the lexicographically smallest one.
Approach 1: Divide and Conquer Grid Evaluation (O(n * 2500) time, O(1) space)
The search space for valid coordinates is bounded because tower coordinates are within a small grid (0 to 50). You can treat the grid as a set of independent regions and evaluate signal quality for each candidate coordinate. For every point (x, y), iterate through all towers, compute the Euclidean distance, and add signal strength if the tower lies within the radius. This effectively divides the problem into many small independent computations and aggregates results to find the maximum. Despite the nested loops, the grid size is constant (51 × 51), so the approach runs efficiently in practice. The main operations are simple iteration, distance calculation, and integer flooring.
Approach 2: Dynamic Programming with Precomputed Contributions (O(n * 2500) time, O(2500) space)
This variation reduces repeated calculations by storing signal contributions for grid coordinates. For each tower, iterate over all grid points within the radius and update a 2D matrix representing accumulated network quality. The matrix acts as a dynamic programming table where dp[x][y] stores the total signal received at that coordinate so far. Each tower contributes floor(q / (1 + distance)) to nearby cells. After processing all towers, scan the table to find the coordinate with the highest signal value. This approach organizes the computation around tower updates instead of coordinate evaluation, which often improves cache locality and code clarity.
Recommended for interviews: The enumeration-based solution is what most interviewers expect. It demonstrates clear reasoning about bounded search spaces and straightforward implementation. Start with the brute-force grid scan to show correctness, then discuss how precomputing contributions with a DP-style grid reduces repeated work. Problems like this frequently appear in discussions around Array traversal and geometric Enumeration, with occasional optimization using Dynamic Programming style accumulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer Grid Evaluation | O(n * 2500) | O(1) | Best when the coordinate grid is small and bounded. Simple brute-force enumeration works efficiently. |
| Dynamic Programming with Accumulated Grid | O(n * 2500) | O(2500) | Useful when organizing updates by tower contributions or when storing intermediate signal totals for clarity. |