1620. Coordinate With Maximum Network Quality LeetCode Solution
In this guide, you will get 1620. Coordinate With Maximum Network Quality LeetCode Solution with the best time and space complexity. The solution to Coordinate With Maximum Network Quality problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Coordinate With Maximum Network Quality
You are given an array of network towers towers, where towers[i] = [xi, yi, qi] denotes the ith network tower with location (xi, yi) and quality factor qi. All the coordinates are integral coordinates on the X-Y plane, and the distance between the two coordinates is the Euclidean distance.
You are also given an integer radius where a tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.
The signal quality of the ith tower at a coordinate (x, y) is calculated with the formula ⌊qi / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.
Return the array [cx, cy] representing the integral coordinate (cx, cy) where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum non-negative coordinate.
Note:
A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either:
x1 < x2, or
x1 == x2 and y1 < y2.
⌊val⌋ is the greatest integer less than or equal to val (the floor function).
Example 1:
Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: 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]
Explanation: 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]
Explanation: Coordinate (1, 2) has the highest network quality.
1620. Coordinate With Maximum Network Quality LeetCode Solution in C++
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));
}
}; /* code provided by PROGIEZ */
1620. Coordinate With Maximum Network Quality LeetCode Solution in Java
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));
}
} // code provided by PROGIEZ
1620. Coordinate With Maximum Network Quality LeetCode Solution in Python
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 # code by PROGIEZ
