# 1620. Coordinate With Maximum Network Quality

• Time: $O(50^2n) = O(n)$
• Space: $O(1)$
  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 30 31 32 33 class Solution { public: vector bestCoordinate(vector>& towers, int radius) { constexpr int kMax = 50; const int n = towers.size(); vector ans(2); int maxQuality = 0; for (int i = 0; i <= kMax; ++i) for (int j = 0; j <= kMax; ++j) { int qualitySum = 0; for (const vector& tower : towers) { const double d = dist(tower, i, j); if (d <= radius) { const int q = tower[2]; qualitySum += static_cast(q / (1 + d)); } } if (qualitySum > maxQuality) { maxQuality = qualitySum; ans = {i, j}; } } return ans; } private: // Returns the distance between the tower and the coordinate. double dist(const vector& tower, int i, int j) { return sqrt(pow(tower[0] - i, 2) + pow(tower[1] - j, 2)); } }; 
  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 30 31 32 33 class Solution { public int[] bestCoordinate(int[][] towers, int radius) { final int kMax = 50; final int n = towers.length; int[] ans = new int[2]; int maxQuality = 0; for (int i = 0; i <= kMax; ++i) { for (int j = 0; j <= kMax; ++j) { int qualitySum = 0; for (int[] tower : towers) { double d = dist(tower, i, j); if (d <= radius) { final int q = tower[2]; qualitySum += (int) (q / (1 + d)); } } if (qualitySum > maxQuality) { maxQuality = qualitySum; ans[0] = i; ans[1] = j; } } } return ans; } // Returns the distance between the tower and the coordinate. private double dist(int[] tower, int i, int j) { return Math.sqrt(Math.pow(tower[0] - i, 2) + Math.pow(tower[1] - j, 2)); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]: kMax = 50 n = len(towers) ans = [0] * 2 maxQuality = 0 def dist(tower: List[int], i: int, j: int) -> float: """Returns the distance between the tower and the coordinate.""" return math.sqrt((tower[0] - i)**2 + (tower[1] - j)**2) for i in range(kMax + 1): for j in range(kMax + 1): qualitySum = 0 for tower in towers: q = tower[2] d = dist(tower, i, j) if d <= radius: qualitySum += int(q / (1 + d)) if qualitySum > maxQuality: maxQuality = qualitySum ans = [i, j] return ans