Coordinate With Maximum Network Quality

This problem requires us to calculate the total network quality for each coordinate in the given range and return the coordinate with the maximum network quality.

Approach:

  1. The possible x and y coordinates will be between 0 and 50 inclusive as per the constraints.
  2. For each of these possible coordinates, we calculate the network quality using the given formula.
  3. We keep track of the maximum network quality and the corresponding coordinate.
  4. We return the coordinate with the maximum network quality.

Let’s implement this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:

        def get_quality(x, y, tower):
            # Calculate distance between (x, y) and the tower
            d = ((x - tower[0]) ** 2 + (y - tower[1]) ** 2) ** 0.5

            # If d > radius, quality contribution from this tower is 0
            if d > radius:
                return 0

            # Return quality using the formula
            return tower[2] // (1 + d)

        max_quality = -1
        best_coordinate = [0, 0]

        # Loop through all possible coordinates
        for x in range(51):  # as x and y can be between 0 and 50
            for y in range(51):
                current_quality = sum(get_quality(x, y, tower) for tower in towers)

                # Check if current_quality is greater than max_quality or 
                # if they are equal, then check for lexicographically smaller coordinate
                if current_quality > max_quality or (current_quality == max_quality and [x, y] < best_coordinate):
                    max_quality = current_quality
                    best_coordinate = [x, y]

        return best_coordinate

Here’s a breakdown:

  • get_quality function calculates the signal quality from a particular tower to a point (x, y).
  • For every coordinate (x, y), we loop through all towers to calculate the total network quality at that coordinate.
  • We update the maximum network quality and corresponding coordinate as needed.
  • Finally, we return the coordinate with the maximum network quality.