{x}
blog image

Coordinate With Maximum Network Quality

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:

  • A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either:
    • x1 < x2, or
    • x1 == 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 <= 50
  • towers[i].length == 3
  • 0 <= xi, yi, qi <= 50
  • 1 <= radius <= 50

Solution Explanation for Coordinate With Maximum Network Quality

This problem requires finding the coordinate (x, y) that maximizes the network quality, which is the sum of signal qualities from all reachable towers. The signal quality from a tower is calculated using the floor function and the distance to the coordinate. The solution employs a brute-force approach, iterating through all possible coordinates within a reasonable range.

Approach

  1. Iteration: The solution iterates through all possible x and y coordinates from 0 to 50 (inclusive), as the problem constraints specify that coordinates are non-negative and at most 50.

  2. Signal Quality Calculation: For each coordinate (x, y), it calculates the network quality by iterating through each tower.

    • Distance: The Euclidean distance between the current coordinate (x, y) and the tower's location (xi, yi) is computed.
    • Reachability: If the distance is less than or equal to the given radius, the tower is considered reachable.
    • Signal Quality: The signal quality from the reachable tower is calculated using the formula ⌊q<sub>i</sub> / (1 + d)⌋, where q<sub>i</sub> is the tower's quality factor and d is the distance. The floor function (represented by Math.floor() in Java, floor() in C++, and math.Floor() in Go) is used to find the greatest integer less than or equal to the result.
    • Summation: The signal qualities from all reachable towers are summed to obtain the network quality for the current coordinate.

  3. Maximum Network Quality: The solution keeps track of the maximum network quality encountered so far and the corresponding coordinate. If a coordinate yields a higher network quality than the current maximum, it updates the maximum and the corresponding coordinate.

  4. Lexicographical Minimum: If multiple coordinates have the same maximum network quality, the solution implicitly returns the lexicographically minimum coordinate due to the order of iteration (it checks coordinates in increasing order of x and then y).

  5. Return Value: Finally, the solution returns the coordinate with the maximum network quality.

Time and Space Complexity

  • Time Complexity: O(n * 50 * 50), where n is the number of towers. The solution iterates through all possible coordinates (51 x 51 = 2601) and for each coordinate it iterates through all towers. This gives a time complexity dominated by the nested loops.

  • Space Complexity: O(1). The solution uses a constant amount of extra space to store the maximum network quality and the corresponding coordinate.

Code Examples (with detailed comments)

The provided code examples in Python, Java, C++, and Go all implement this brute-force approach. The code is self-explanatory with inline comments, highlighting the steps mentioned in the approach section. The primary differences between the languages are mainly in syntax and standard library functions used for mathematical operations (like sqrt, floor).

This solution is straightforward and easy to understand, but it's not the most efficient for very large input sizes. More efficient solutions might involve more sophisticated techniques like using spatial data structures (e.g., k-d trees) to speed up the nearest-neighbor search. However, for the given constraints (number of towers <= 50, coordinates <= 50), this brute-force approach is sufficient and performs reasonably well.