#1620

Medium

LeetCode Problem Workspace

Coordinate With Maximum Network Quality

Determine the coordinate with the maximum network quality by summing signal strengths from all reachable towers efficiently using enumeration.

array enumeration

Problem Statement

You are given a list of network towers, where each tower is represented as [xi, yi, qi] indicating its X-Y coordinates and quality factor. A tower's signal reaches coordinates within a given radius, and the quality at any coordinate is determined by the formula ⌊qi / (1 + distance)⌋. The distance is Euclidean, and signals beyond the radius are ignored.

Your task is to identify the integral coordinate on the X-Y plane where the network quality, calculated as the sum of all reachable towers' signal contributions, is maximized. If multiple coordinates yield the same maximum quality, return the coordinate with the smallest X value, and if still tied, the smallest Y value.

Examples

Example 1

Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2

Output: [2,1]

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]

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]

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 Approach

Brute Force Enumeration

Iterate over all integral coordinates within the bounding box of tower positions. For each coordinate, sum the signal contributions from towers within the radius. This directly applies the array plus enumeration pattern, leveraging the small constraints to compute total network quality for each point.

Distance Calculation Optimization

Precompute squared distances to avoid repeated square roots when checking if a tower is within the radius. For each coordinate, accumulate signals only from towers satisfying distance ≤ radius. This reduces redundant computation and aligns with the pattern by carefully managing array iteration and arithmetic.

Tie-breaking and Result Selection

While tracking the maximum network quality, maintain the coordinate with the smallest X (and then smallest Y) in case of ties. This ensures correct handling of failure modes where multiple coordinates yield identical total quality, preserving the problem-specific trade-off between enumeration thoroughness and correct selection.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O((maxX*maxY)*n) where maxX and maxY are the maximum coordinates and n is the number of towers, since each coordinate may check every tower. Space complexity is O(1) extra beyond input, though temporary storage for distances or maximum tracking is constant.

What Interviewers Usually Probe

Watch for missing tie-breaking when multiple coordinates have the same network quality.
Confirm that signal calculations use integer division as specified by ⌊qi / (1 + distance)⌋.
Expect discussion on whether iterating all coordinates is feasible under small constraints.

Common Pitfalls or Variants

Common pitfalls

Forgetting the radius cutoff, leading to including towers beyond reach.
Miscomputing Euclidean distance or applying floating-point division incorrectly.
Ignoring tie-breaking rules for X and Y when multiple coordinates yield the same quality.

Follow-up variants

Maximize network quality with non-integral coordinates, requiring more precise distance handling.
Include signal decay factors or weights per tower, adding complexity to the sum computation.
Compute top k coordinates with highest network quality instead of just the maximum.

FAQ

What formula is used to compute a tower's contribution at a coordinate?

The contribution is ⌊qi / (1 + distance)⌋, where qi is the tower's quality and distance is the Euclidean distance to the coordinate.

Do we consider all coordinates or only around towers?

All integral coordinates within the bounding box of tower positions should be considered due to the small constraints.

How are ties resolved when multiple coordinates have the same network quality?

Choose the coordinate with the smallest X value, and if still tied, the smallest Y value.

Why is this an array plus enumeration problem?

Each coordinate is enumerated and for each, the array of towers is iterated to sum signal contributions, exemplifying array plus enumeration.

Can floating-point errors affect the solution?

Yes, but using integer math with distance comparisons or proper rounding avoids inaccuracies when applying ⌊qi / (1 + distance)⌋.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:
        mx = 0
        ans = [0, 0]
        for i in range(51):
            for j in range(51):
                t = 0
                for x, y, q in towers:
                    d = ((x - i) ** 2 + (y - j) ** 2) ** 0.5
                    if d <= radius:
                        t += floor(q / (1 + d))
                if t > mx:
                    mx = t
                    ans = [i, j]
        return ans

Continue Practicing

#1601 maximum number of achievable transfer requests #1566 detect pattern of length m repeated k or more times #1534 count good triplets