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 theintegral coordinate _(cx, cy)where thenetwork 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).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2020/09/22/untitled-diagram.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

1
2
3

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

1
2
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

Solution

Method 1 – Brute Force Enumeration 1

Intuition

The best coordinate must be an integer point within the bounding box of all towers, since the signal quality only changes at integer coordinates. We can check all integer points in this range and compute the total network quality for each, picking the one with the highest quality (and lexicographically smallest in case of ties).

Approach

  1. Find the minimum and maximum x and y among all towers to define the bounding box.
  2. For each integer coordinate (x, y) in this box:
    • For each tower, compute the Euclidean distance to (x, y).
    • If the distance is within radius, add the tower’s signal quality to the total.
  3. Track the coordinate with the highest total quality (and lexicographically smallest if tied).
  4. Return the best coordinate.

Code

 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

class Solution {
public:
    vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
        int minX = INT_MAX, minY = INT_MAX, maxX = INT_MIN, maxY = INT_MIN;
        for (auto& t : towers) {
            minX = min(minX, t[0]);
            minY = min(minY, t[1]);
            maxX = max(maxX, t[0]);
            maxY = max(maxY, t[1]);
        }
        vector<int> ans = {0, 0};
        int maxQ = 0;
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                int q = 0;
                for (auto& t : towers) {
                    int dx = t[0] - x, dy = t[1] - y;
                    double d = sqrt(dx * dx + dy * dy);
                    if (d <= radius) q += floor(t[2] / (1 + d));
                }
                if (q > maxQ || (q == maxQ && (x < ans[0] || (x == ans[0] && y < ans[1])))) {
                    maxQ = q;
                    ans = {x, y};
                }
            }
        }
        return ans;
    }
};
 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

func bestCoordinate(towers [][]int, radius int) []int {
    minX, minY, maxX, maxY := towers[0][0], towers[0][1], towers[0][0], towers[0][1]
    for _, t := range towers {
        if t[0] < minX { minX = t[0] }
        if t[1] < minY { minY = t[1] }
        if t[0] > maxX { maxX = t[0] }
        if t[1] > maxY { maxY = t[1] }
    }
    ans := []int{0, 0}
    maxQ := 0
    for x := minX; x <= maxX; x++ {
        for y := minY; y <= maxY; y++ {
            q := 0
            for _, t := range towers {
                dx, dy := t[0]-x, t[1]-y
                d := math.Sqrt(float64(dx*dx + dy*dy))
                if d <= float64(radius) {
                    q += int(math.Floor(float64(t[2]) / (1 + d)))
                }
            }
            if q > maxQ || (q == maxQ && (x < ans[0] || (x == ans[0] && y < ans[1]))) {
                maxQ = q
                ans = []int{x, y}
            }
        }
    }
    return ans
}
 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

class Solution {
    public int[] bestCoordinate(int[][] towers, int radius) {
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
        for (int[] t : towers) {
            minX = Math.min(minX, t[0]);
            minY = Math.min(minY, t[1]);
            maxX = Math.max(maxX, t[0]);
            maxY = Math.max(maxY, t[1]);
        }
        int[] ans = new int[2];
        int maxQ = 0;
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                int q = 0;
                for (int[] t : towers) {
                    int dx = t[0] - x, dy = t[1] - y;
                    double d = Math.sqrt(dx * dx + dy * dy);
                    if (d <= radius) q += Math.floorDiv(t[2], (int)(1 + d));
                }
                if (q > maxQ || (q == maxQ && (x < ans[0] || (x == ans[0] && y < ans[1])))) {
                    maxQ = q;
                    ans[0] = x; ans[1] = y;
                }
            }
        }
        return ans;
    }
}
 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

class Solution {
    fun bestCoordinate(towers: Array<IntArray>, radius: Int): IntArray {
        var minX = towers[0][0]
        var minY = towers[0][1]
        var maxX = towers[0][0]
        var maxY = towers[0][1]
        for (t in towers) {
            minX = minOf(minX, t[0])
            minY = minOf(minY, t[1])
            maxX = maxOf(maxX, t[0])
            maxY = maxOf(maxY, t[1])
        }
        var ans = intArrayOf(0, 0)
        var maxQ = 0
        for (x in minX..maxX) {
            for (y in minY..maxY) {
                var q = 0
                for (t in towers) {
                    val dx = t[0] - x
                    val dy = t[1] - y
                    val d = Math.sqrt((dx * dx + dy * dy).toDouble())
                    if (d <= radius) q += Math.floor(t[2] / (1 + d)).toInt()
                }
                if (q > maxQ || (q == maxQ && (x < ans[0] || (x == ans[0] && y < ans[1])))) {
                    maxQ = q
                    ans = intArrayOf(x, y)
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def bestCoordinate(self, towers: list[list[int]], radius: int) -> list[int]:
        min_x = min(t[0] for t in towers)
        max_x = max(t[0] for t in towers)
        min_y = min(t[1] for t in towers)
        max_y = max(t[1] for t in towers)
        ans = [0, 0]
        max_q = 0
        for x in range(min_x, max_x + 1):
            for y in range(min_y, max_y + 1):
                q = 0
                for tx, ty, tq in towers:
                    d = ((tx - x) ** 2 + (ty - y) ** 2) ** 0.5
                    if d <= radius:
                        q += int(tq // (1 + d))
                if q > max_q or (q == max_q and (x < ans[0] or (x == ans[0] and y < ans[1]))):
                    max_q = q
                    ans = [x, y]
        return ans
 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

impl Solution {
    pub fn best_coordinate(towers: Vec<Vec<i32>>, radius: i32) -> Vec<i32> {
        let (mut min_x, mut max_x) = (towers[0][0], towers[0][0]);
        let (mut min_y, mut max_y) = (towers[0][1], towers[0][1]);
        for t in &towers {
            min_x = min_x.min(t[0]);
            max_x = max_x.max(t[0]);
            min_y = min_y.min(t[1]);
            max_y = max_y.max(t[1]);
        }
        let mut ans = vec![0, 0];
        let mut max_q = 0;
        for x in min_x..=max_x {
            for y in min_y..=max_y {
                let mut q = 0;
                for t in &towers {
                    let dx = t[0] - x;
                    let dy = t[1] - y;
                    let d = ((dx * dx + dy * dy) as f64).sqrt();
                    if d <= radius as f64 {
                        q += (t[2] as f64 / (1.0 + d)).floor() as i32;
                    }
                }
                if q > max_q || (q == max_q && (x < ans[0] || (x == ans[0] && y < ans[1]))) {
                    max_q = q;
                    ans = vec![x, y];
                }
            }
        }
        ans
    }
}
 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

class Solution {
    bestCoordinate(towers: number[][], radius: number): number[] {
        let minX = towers[0][0], maxX = towers[0][0], minY = towers[0][1], maxY = towers[0][1];
        for (const t of towers) {
            minX = Math.min(minX, t[0]);
            maxX = Math.max(maxX, t[0]);
            minY = Math.min(minY, t[1]);
            maxY = Math.max(maxY, t[1]);
        }
        let ans = [0, 0], maxQ = 0;
        for (let x = minX; x <= maxX; ++x) {
            for (let y = minY; y <= maxY; ++y) {
                let q = 0;
                for (const [tx, ty, tq] of towers) {
                    const d = Math.sqrt((tx - x) ** 2 + (ty - y) ** 2);
                    if (d <= radius) q += Math.floor(tq / (1 + d));
                }
                if (q > maxQ || (q === maxQ && (x < ans[0] || (x === ans[0] && y < ans[1])))) {
                    maxQ = q;
                    ans = [x, y];
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * W * H), where n is the number of towers, and W, H are the width and height of the bounding box. For each integer coordinate, we check all towers.
  • 🧺 Space complexity: O(1), as only a constant amount of space is used for tracking the answer.