Problem Description

You are given a list of towers where each tower is represented as [xi, yi, qi]:

• (xi, yi) is the coordinate of the ith tower on a 2D grid.
• qi is the quality factor of the ith tower.

The network quality at a coordinate (x, y) is determined by summing the signal contributions from all towers within a distance of radius. The contribution from the ith tower is calculated as:
floor(qi / (1 + distance)) if distance between (x, y) and (xi, yi) is less than or equal to radius, otherwise 0.

You need to find the coordinate with the maximum network quality. If there are multiple such coordinates, return the one with the smallest x, and if there is still a tie, the smallest y.

Constraints:

• 1 ≤ towers.length ≤ 50
• 0 ≤ xi, yi, qi ≤ 50
• 1 ≤ radius ≤ 50
• There is at least one tower.

Thought Process

At first glance, we need to find the point in the 2D grid (within the bounds of the towers) that receives the best combined signal from all towers within a certain radius. Each tower’s signal diminishes with distance, and only towers within the specified radius contribute.

The brute-force approach is to check every possible integer coordinate in the grid, sum the contributions from all towers, and keep track of the best one. Given the constraints (small grid and tower count), this is feasible.

We also need to handle ties, always preferring the smallest x and then y values.

The key is to limit our search to the bounding rectangle that contains all towers, as no other point can have a better signal from all towers.

Solution Approach

We will follow these steps:

1. Find Grid Bounds: Identify the minimum and maximum x and y values among all towers. We only need to consider points within this rectangle since signals outside won’t be better.
2. Iterate All Integer Coordinates: For each integer coordinate (x, y) within the bounds, calculate the total network quality by summing the contributions from all towers.
3. Signal Contribution: For each tower, compute the Euclidean distance to (x, y). If the distance is within radius, add floor(qi / (1 + distance)) to the total.
4. Track Maximum: Keep track of the coordinate with the highest total quality. In case of a tie, update only if the new coordinate has a smaller x or (if x is the same) a smaller y.

This approach is efficient due to the small constraints and guarantees correctness by exhaustive search within the relevant region.

Example Walkthrough

Example Input:
towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2

• The tower coordinates range from x=1 to x=3, and y=1 to y=2.
• For each integer point in this rectangle, we calculate the total network quality:
  • For (1,1):
    • Distance to (1,2): 1 → contributes floor(5/2) = 2
    • Distance to (2,1): 1 → floor(7/2) = 3
    • Distance to (3,1): 2 → floor(9/3) = 3
    • Total: 2 + 3 + 3 = 8
  • For (2,1) (repeat similar calculations):
    • Distance to (1,2): ~1.41 → floor(5/2.41) = 2
    • Distance to (2,1): 0 → floor(7/1) = 7
    • Distance to (3,1): 1 → floor(9/2) = 4
    • Total: 2 + 7 + 4 = 13
  • Similar calculations for all other points.
• The coordinate with the highest total is (2,1) with a quality of 13.

Time and Space Complexity

• Brute-force approach:
  • For each integer coordinate in the bounding rectangle (at most 51x51 = 2601 points), for each tower (≤50), we compute the contribution.
  • Time Complexity: O(N*M), where N is the number of candidate coordinates (≤2601) and M is the number of towers (≤50). This is at most about 130,000 operations, which is efficient.
  • Space Complexity: O(1), ignoring input and output, as we only track the current best coordinate and quality.
• Optimized approaches: Not necessary due to small constraints.

Summary

This problem is a classic example of a manageable brute-force search due to small input sizes. By limiting our search to the bounding rectangle of towers and calculating each possible coordinate’s signal quality, we ensure correctness and efficiency. The solution elegantly handles ties and leverages simple mathematical operations to determine the optimal coordinate.

Code Implementation

from math import sqrt, floor

class Solution:
    def bestCoordinate(self, towers, radius):
        # Find bounds
        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)

        best = [0, 0]
        max_quality = -1

        for x in range(min_x, max_x + 1):
            for y in range(min_y, max_y + 1):
                total = 0
                for xi, yi, qi in towers:
                    dist = sqrt((x - xi) ** 2 + (y - yi) ** 2)
                    if dist <= radius:
                        total += floor(qi / (1 + dist))
                if total > max_quality or (total == max_quality and (x < best[0] or (x == best[0] and y < best[1]))):
                    best = [x, y]
                    max_quality = total
        return best
      

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
        int min_x = 51, max_x = 0, min_y = 51, max_y = 0;
        for (auto& t : towers) {
            min_x = min(min_x, t[0]);
            max_x = max(max_x, t[0]);
            min_y = min(min_y, t[1]);
            max_y = max(max_y, t[1]);
        }
        vector<int> best = {0, 0};
        int max_quality = -1;
        for (int x = min_x; x <= max_x; ++x) {
            for (int y = min_y; y <= max_y; ++y) {
                int total = 0;
                for (auto& t : towers) {
                    double dist = sqrt((x - t[0]) * (x - t[0]) + (y - t[1]) * (y - t[1]));
                    if (dist <= radius) {
                        total += (int)(t[2] / (1 + dist));
                    }
                }
                if (total > max_quality || (total == max_quality && (x < best[0] || (x == best[0] && y < best[1])))) {
                    best = {x, y};
                    max_quality = total;
                }
            }
        }
        return best;
    }
};
      

import java.util.*;

class Solution {
    public int[] bestCoordinate(int[][] towers, int radius) {
        int minX = 51, maxX = 0, minY = 51, maxY = 0;
        for (int[] t : 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]);
        }
        int[] best = new int[2];
        int maxQuality = -1;

        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                int total = 0;
                for (int[] t : towers) {
                    double dist = Math.sqrt((x - t[0]) * (x - t[0]) + (y - t[1]) * (y - t[1]));
                    if (dist <= radius) {
                        total += (int)(t[2] / (1 + dist));
                    }
                }
                if (total > maxQuality || (total == maxQuality && (x < best[0] || (x == best[0] && y < best[1])))) {
                    best[0] = x;
                    best[1] = y;
                    maxQuality = total;
                }
            }
        }
        return best;
    }
}
      

var bestCoordinate = function(towers, radius) {
    let minX = 51, maxX = 0, minY = 51, maxY = 0;
    for (const [xi, yi] of towers) {
        minX = Math.min(minX, xi);
        maxX = Math.max(maxX, xi);
        minY = Math.min(minY, yi);
        maxY = Math.max(maxY, yi);
    }
    let best = [0, 0], maxQuality = -1;
    for (let x = minX; x <= maxX; ++x) {
        for (let y = minY; y <= maxY; ++y) {
            let total = 0;
            for (const [xi, yi, qi] of towers) {
                let dist = Math.sqrt((x - xi) ** 2 + (y - yi) ** 2);
                if (dist <= radius) {
                    total += Math.floor(qi / (1 + dist));
                }
            }
            if (total > maxQuality || (total === maxQuality && (x < best[0] || (x === best[0] && y < best[1])))) {
                best = [x, y];
                maxQuality = total;
            }
        }
    }
    return best;
};