LeetCode 1620: Coordinate With Maximum Network Quality
Problem Description
Explanation:
- We iterate over each integral coordinate within the given bounds and calculate the network quality at that coordinate by summing up the signal qualities from all reachable towers.
- We keep track of the coordinate with the maximum network quality seen so far and return it in the end.
Time Complexity: O(n^3), where n is the maximum value of the coordinates (50 in this case). Space Complexity: O(1)
:
Solutions
class Solution {
public int[] bestCoordinate(int[][] towers, int radius) {
int maxQuality = 0;
int[] bestCoordinate = new int[]{0, 0};
for (int x = 0; x <= 50; x++) {
for (int y = 0; y <= 50; y++) {
int quality = 0;
for (int[] tower : towers) {
int dist = (x - tower[0]) * (x - tower[0]) + (y - tower[1]) * (y - tower[1]);
if (dist <= radius * radius) {
quality += tower[2] / (1 + Math.sqrt(dist));
}
}
if (quality > maxQuality) {
maxQuality = quality;
bestCoordinate = new int[]{x, y};
}
}
}
return bestCoordinate;
}
}Loading editor...