# Coordinate With Maximum Network Quality
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/coordinate-with-maximum-network-quality)
Canonical: https://scaleengineer.com/dsa/problems/coordinate-with-maximum-network-quality
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Lyft](https://scaleengineer.com/companies/lyft), [peak6](https://scaleengineer.com/companies/peak6)
---
## Problem
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:**

![](https://assets.glich.co/dsa/coordinate-with-maximum-network-quality/image0.png) 

**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.

**Constraints:**

* `1 <= towers.length <= 50`
* `towers[i].length == 3`
* `0 <= xi, yi, qi <= 50`
* `1 <= radius <= 50`

# Approaches
## Brute-Force Grid Search on a Fixed Area
This approach involves checking every possible integer coordinate within a sufficiently large, pre-defined grid to find the point with the maximum network quality. The key idea is that the optimal point cannot be infinitely far from all towers, as the signal quality drops to zero beyond the given radius. By choosing a large enough fixed grid, we can guarantee that the optimal coordinate is included in our search.
**Time:** O(C² * N), where `C` is the side length of the fixed search area (e.g., 101 based on constraints) and `N` is the number of towers. The algorithm iterates through `C*C` points, and for each point, it iterates through all `N` towers. · **Space:** O(1) extra space, as we only need a few variables to store the maximum quality and the best coordinate.
**Pros:** The approach is simple to understand and implement.; It is guaranteed to find the correct answer, provided the fixed search area is large enough to contain the optimal point.
**Cons:** It is inefficient because it may search a much larger area than necessary, especially if the tower coordinates and radius are small.; The choice of the fixed boundary is somewhat arbitrary and not tailored to the specific input, which can lead to wasted computation.
### Explanation
We define a search grid that is guaranteed to contain the optimal coordinate. Given the constraints (`0 <= xi, yi <= 50`, `radius <= 50`), a safe but potentially oversized grid could be from `(0,0)` to `(150, 150)`. This covers all towers and any point within `radius` of them, and then some.

The algorithm iterates through each integer point `(x, y)` in this fixed grid. For each point, it calculates the total network quality by summing up the signal qualities from all reachable towers. A tower at `(tx, ty)` with quality `q` is reachable if the Euclidean distance `d` to `(x, y)` is not greater than `radius`. The signal quality is `floor(q / (1 + d))`. We keep track of the maximum quality found so far and the coordinate that produced it. Because we iterate through `x` and then `y` in increasing order, the first time we encounter the maximum quality, we are guaranteed to have the lexicographically smallest coordinate. We update the result only when a strictly greater quality is found.

```java
class Solution {
    public int[] bestCoordinate(int[][] towers, int radius) {
        int maxQuality = -1;
        int[] bestCoordinate = {0, 0};
        // A fixed, large enough bound that covers the worst-case constraints.
        int searchBound = 101; 

        for (int x = 0; x < searchBound; x++) {
            for (int y = 0; y < searchBound; y++) {
                int currentQuality = 0;
                for (int[] tower : towers) {
                    int tx = tower[0];
                    int ty = tower[1];
                    int q = tower[2];
                    
                    double dist = Math.sqrt(Math.pow(x - tx, 2) + Math.pow(y - ty, 2));
                    
                    if (dist <= radius) {
                        currentQuality += (int) Math.floor(q / (1 + dist));
                    }
                }
                
                if (currentQuality > maxQuality) {
                    maxQuality = currentQuality;
                    bestCoordinate[0] = x;
                    bestCoordinate[1] = y;
                }
            }
        }
        return bestCoordinate;
    }
}
```
### Algorithm
- Initialize `maxQuality` to -1 and `bestCoordinate` to `[0, 0]`.
- Define a fixed, sufficiently large search boundary, for example, `max_coord = 150`, to ensure it covers all possible optimal locations given the problem's constraints.
- Loop through each integer coordinate `(x, y)` from `(0, 0)` up to `(max_coord, max_coord)`.
- For each coordinate `(x, y)`, calculate its `currentQuality`:
    - Initialize `currentQuality = 0`.
    - For each tower `[tx, ty, q]`:
        - Calculate the Euclidean distance `d` between `(x, y)` and `(tx, ty)`.
        - If `d` is less than or equal to `radius`, add the signal quality `floor(q / (1 + d))` to `currentQuality`.
- If `currentQuality` is greater than `maxQuality`, update `maxQuality` to `currentQuality` and `bestCoordinate` to `[x, y]`.
- After checking all points, return `bestCoordinate`.

## Optimized Grid Search on a Dynamically Bounded Area
This approach improves upon the brute-force method by intelligently determining the search area. Instead of using a large fixed grid, it calculates a tighter bounding box based on the actual locations of the towers and the given radius. This avoids unnecessary computations for points that are guaranteed to have zero network quality, making the solution more efficient.
**Time:** O((X_max + R) * (Y_max + R) * N), where `X_max` and `Y_max` are the maximum coordinates of towers, `R` is the radius, and `N` is the number of towers. Given the problem constraints, this is highly efficient. · **Space:** O(1) extra space. We only use a few variables to store the maximum coordinates, maximum quality, and the result.
**Pros:** More efficient than the fixed-grid approach, as it tailors the search space to the input, avoiding redundant checks.; Guaranteed to be correct and is optimal for the given constraints.; Remains simple to implement and understand.
**Cons:** The time complexity still depends polynomially on the maximum coordinate values and the radius, which could be slow for much larger constraints (though it's fine for this problem).
### Explanation
The core idea is that any point with a non-zero network quality must be within `radius` distance of at least one tower. We can leverage this to shrink our search space. First, we iterate through the towers to find the maximum `x` and `y` coordinates, let's call them `maxX` and `maxY`. Any point `(x, y)` with `x > maxX + radius` or `y > maxY + radius` will be more than `radius` distance away from any tower `(tx, ty)` (since `tx <= maxX` and `ty <= maxY`). Therefore, such points will have a network quality of 0 and don't need to be checked.

This observation allows us to confine our search to the rectangle defined by `x` from `0` to `maxX + radius` and `y` from `0` to `maxY + radius`. The rest of the algorithm is the same as the basic brute-force approach: iterate through all integer points in this dynamically determined grid, calculate the network quality for each, and keep track of the coordinate with the maximum quality. The lexicographically smallest tie-breaking rule is handled naturally by the loop order (`for x... for y...`).

```java
class Solution {
    public int[] bestCoordinate(int[][] towers, int radius) {
        int maxX = 0;
        int maxY = 0;
        for (int[] tower : towers) {
            maxX = Math.max(maxX, tower[0]);
            maxY = Math.max(maxY, tower[1]);
        }

        int maxQuality = -1;
        int[] bestCoordinate = {0, 0};
        int radiusSquared = radius * radius;

        for (int x = 0; x <= maxX + radius; x++) {
            for (int y = 0; y <= maxY + radius; y++) {
                int currentQuality = 0;
                for (int[] tower : towers) {
                    int tx = tower[0];
                    int ty = tower[1];
                    int q = tower[2];
                    
                    int dx = x - tx;
                    int dy = y - ty;
                    int dSquared = dx * dx + dy * dy;
                    
                    if (dSquared <= radiusSquared) {
                        double dist = Math.sqrt(dSquared);
                        currentQuality += (int) Math.floor(q / (1.0 + dist));
                    }
                }
                
                if (currentQuality > maxQuality) {
                    maxQuality = currentQuality;
                    bestCoordinate[0] = x;
                    bestCoordinate[1] = y;
                }
            }
        }
        return bestCoordinate;
    }
}
```
### Algorithm
- First, determine the maximum x-coordinate (`maxX`) and y-coordinate (`maxY`) among all towers.
- Initialize `maxQuality` to -1 and `bestCoordinate` to `[0, 0]`.
- The search boundary for `x` will be from `0` to `maxX + radius`, and for `y` from `0` to `maxY + radius`.
- Loop through each integer coordinate `(x, y)` within this dynamically determined boundary.
- For each coordinate `(x, y)`, calculate its `currentQuality`:
    - Initialize `currentQuality = 0`.
    - For each tower `[tx, ty, q]`:
        - Calculate the squared distance `d_sq = (x - tx)² + (y - ty)²`.
        - If `d_sq` is less than or equal to `radius²`, the tower is reachable.
        - Calculate the actual distance `d = sqrt(d_sq)` and add `floor(q / (1 + d))` to `currentQuality`.
- If `currentQuality` is greater than `maxQuality`, update `maxQuality` to `currentQuality` and `bestCoordinate` to `[x, y]`.
- After checking all points in the bounded grid, return `bestCoordinate`.

# Solutions
### Java

```java
class Solution {
public
  int[] bestCoordinate(int[][] towers, int radius) {
    int mx = 0;
    int[] ans = new int[]{0, 0};
    for (int i = 0; i < 51; ++i) {
      for (int j = 0; j < 51; ++j) {
        int t = 0;
        for (var e : towers) {
          double d =
              Math.sqrt((i - e[0]) * (i - e[0]) + (j - e[1]) * (j - e[1]));
          if (d <= radius) {
            t += Math.floor(e[2] / (1 + d));
          }
        }
        if (mx < t) {
          mx = t;
          ans = new int[]{i, j};
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> bestCoordinate(vector<vector<int>> &towers, int radius) {
    int mx = 0;
    vector<int> ans = {0, 0};
    for (int i = 0; i < 51; ++i) {
      for (int j = 0; j < 51; ++j) {
        int t = 0;
        for (auto &e : towers) {
          double d = sqrt((i - e[0]) * (i - e[0]) + (j - e[1]) * (j - e[1]));
          if (d <= radius) {
            t += floor(e[2] / (1 + d));
          }
        }
        if (mx < t) {
          mx = t;
          ans = {i, j};
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]: mx = 0 ans = [0, 0] for i in range(51): for j in range(51): t = 0 for x, y, q in towers: d = ((x - i) ** 2 + (y - j) ** 2) ** 0.5 if d <= radius: t += floor(q / (1 + d)) if t > mx: mx = t ans = [i, j] return ans

```