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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Coordinate With Maximum Network Quality

Number: 1726

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a list of network towers and a radius, each tower provides a signal whose quality at a coordinate (x, y) is calculated as floor(q / (1 + d)), where q is the tower's quality factor and d is the Euclidean distance between the tower and the coordinate. Only towers within the given radius (d <= radius) are considered reachable. The task is to find the integral coordinate where the sum of the signal qualities from all reachable towers is maximized. In case of ties, return the lexicographically smallest coordinate.

Key Insights

  • The search space can be limited by determining the minimum and maximum x and y coordinates from the towers, then expanding these bounds by the radius.
  • For each integral coordinate within this bounding box, calculate the cumulative signal quality from each tower that is reachable.
  • Use the formula floor(q / (1 + d)) for the contribution from each tower where d is computed using the Euclidean distance.
  • Use a brute-force approach since the number of towers and possible grid points (given the constraints) is small.
  • Track the coordinate with the highest network quality, ensuring that if there are ties, the coordinate with the smallest x (and then y) is selected.
  • Avoid floating point issues by computing the distance using math.sqrt.

Space and Time Complexity

Time Complexity: O(grid_area * towers) where grid_area is the area of the bounding box around all towers; worst-case approximately (max_x+radius) * (max_y+radius). Space Complexity: O(1) extra space, aside from input storage.

Solution

The solution iterates over a bounded grid determined by the minimum and maximum coordinates of the towers, expanded by the radius. For each coordinate:

  1. Compute the distance from the coordinate to each tower.
  2. If the distance is within the radius, compute the tower's contribution using floor(q / (1 + d)).
  3. Sum the contributions from all towers.
  4. Update the maximum network quality and store the coordinate if it exceeds the current maximum, or if it ties and is lexicographically smaller. Data structures used include simple variables for tracking maximum quality and the best coordinate while iterating over a fixed grid. The algorithm is straightforward brute force enumeration.

Code Solutions

# Python solution for Coordinate With Maximum Network Quality

import math

def bestCoordinate(towers, radius):
    # Initialize boundaries using the tower coordinates
    min_x = min(tower[0] for tower in towers)
    max_x = max(tower[0] for tower in towers)
    min_y = min(tower[1] for tower in towers)
    max_y = max(tower[1] for tower in towers)
    
    best_quality = -1
    best_coord = [0, 0]
    
    # Expand the grid by radius to cover all potential coordinates
    for x in range(min_x - radius, max_x + radius + 1):
        for y in range(min_y - radius, max_y + radius + 1):
            total_quality = 0
            # Evaluate quality from each tower
            for tx, ty, tq in towers:
                # Calculate the Euclidean distance between (x, y) and tower (tx, ty)
                d = math.sqrt((x - tx) ** 2 + (y - ty) ** 2)
                # Check if tower is within reachable range
                if d <= radius:
                    # Add quality after applying the formula floor(q / (1 + d))
                    total_quality += int(tq / (1 + d))
            # Update the best coordinate based on quality and lexicographical order
            if total_quality > best_quality or (total_quality == best_quality and [x, y] < best_coord):
                best_quality = total_quality
                best_coord = [x, y]
    return best_coord

# Example usage:
towers = [[1,2,5],[2,1,7],[3,1,9]]
radius = 2
print(bestCoordinate(towers, radius))  # Expected output: [2,1]
← Back to All Questions