Skip to content

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<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
    constexpr int kMax = 50;
    const int n = towers.size();
    vector<int> 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<int>& tower : towers) {
          const double d = dist(tower, i, j);
          if (d <= radius) {
            const int q = tower[2];
            qualitySum += static_cast<int>(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<int>& 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