We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Coordinate With Maximum Network Quality

Difficulty: Medium

Problem Description

You are given an array of network 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. 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.

Key Insights

  • The problem requires calculating the network quality based on Euclidean distance from multiple towers.
  • The quality from each tower decreases with distance, following the formula involving the floor function.
  • A brute-force approach can be used due to the manageable size of the input constraints (maximum 50 towers).
  • Lexicographical ordering is needed when multiple coordinates yield the same maximum quality.

Space and Time Complexity

Time Complexity: O(n * r^2) where n is the number of towers and r is the maximum radius (taking into account the grid size from 0 to 50). Space Complexity: O(1) as we only need a few variables to track maximum quality and coordinates.

Solution

The approach involves iterating through all possible integral coordinates within the bounds defined by the towers and the given radius. For each coordinate, we calculate its network quality by checking the distance to each tower. Only towers within the specified radius contribute to the quality. We keep track of the maximum quality found and the corresponding coordinates, ensuring to return the lexicographically smallest coordinate in case of ties.

Code Solutions

def maxCoordinateQuality(towers, radius):
    max_quality = -1
    best_coordinate = (0, 0)

    for x in range(51):  # x coordinates from 0 to 50
        for y in range(51):  # y coordinates from 0 to 50
            total_quality = 0
            for tx, ty, tq in towers:
                distance = ((tx - x) ** 2 + (ty - y) ** 2) ** 0.5
                if distance <= radius:
                    total_quality += tq // (1 + distance)

            if total_quality > max_quality:
                max_quality = total_quality
                best_coordinate = (x, y)
            elif total_quality == max_quality:
                if (x, y) < best_coordinate:
                    best_coordinate = (x, y)

    return list(best_coordinate)
← Back to All Questions