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.
This approach involves breaking the problem into smaller sub-problems, solving each sub-problem independently, and then combining the solutions to solve the original problem. The Divide and Conquer strategy is particularly useful in problems such as sorting algorithms and is often implemented via recursive methods.
The provided solution implements the Merge Sort algorithm using the divide and conquer approach in C. It uses a recursive function mergeSort to divide the array into two halves, sorts them, and then merges them using a helper function merge.
Time Complexity: O(n log n) - The merge sort algorithm divides the array into sub-arrays, sorts and then merges them.
Space Complexity: O(n) - Additional space is used for the temporary arrays during the merge process.
This approach involves solving complex problems by breaking them down into simpler overlapping sub-problems that are solved independently. This technique is used when sub-problems repeat, and the results can be stored to avoid redundant calculations, optimizing time complexity. Dynamic programming can be implemented using either a top-down (memoization) or bottom-up approach.
The Java code demonstrates finding the nth Fibonacci number using a dynamic programming approach with memoization. It stores previously calculated Fibonacci values in a HashMap to prevent redundant computations, thus optimizing the time complexity.
Java
JavaScript
Time Complexity: O(n) - Each Fibonacci number is computed once and stored.
Space Complexity: O(n) - Space is used to store the computed Fibonacci values in a HashMap.
| Approach | Complexity |
|---|---|
| Divide and Conquer | Time Complexity: O(n log n) - The merge sort algorithm divides the array into sub-arrays, sorts and then merges them. |
| Dynamic Programming | Time Complexity: O(n) - Each Fibonacci number is computed once and stored. |
| Default Approach | — |
| 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. |
Coordinate With Maximum Network Quality Leetcode 1620 video • EasyLeetcode • 1,034 views views
Watch 3 more video solutions →Practice Coordinate With Maximum Network Quality with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor