Problem Description

You are given an array of network towers where each tower is represented as [x, y, q] - the tower is located at coordinate (x, y) with quality factor q. All coordinates are integers on a 2D plane.

A tower can reach a coordinate if the Euclidean distance between them is less than or equal to a given radius. The Euclidean distance between two points (x1, y1) and (x2, y2) is calculated as sqrt((x1-x2)² + (y1-y2)²).

For any coordinate (x, y), the signal quality from a reachable tower i is calculated using the formula: ⌊qi / (1 + d)⌋, where d is the distance between the tower and the coordinate, and ⌊⌋ represents the floor function (rounding down to the nearest integer).

The network quality at any coordinate is the sum of signal qualities from all reachable towers at that location.

Your task is to find the integral coordinate (cx, cy) where the network quality is maximum. If multiple coordinates have the same maximum network quality, return the lexicographically smallest non-negative coordinate.

Lexicographic ordering means:

• Coordinate (x1, y1) comes before (x2, y2) if x1 < x2
• If x1 == x2, then (x1, y1) comes before (x2, y2) if y1 < y2

The solution uses a brute force approach by checking all possible coordinates from (0, 0) to (50, 50). For each coordinate, it calculates the total network quality by summing up the signal qualities from all reachable towers. The coordinate with the maximum network quality is tracked, and in case of ties, the lexicographically smallest coordinate is automatically selected due to the iteration order.

Intuition

The key insight is that we need to find the optimal location that maximizes the sum of signal qualities from all towers. Since signal quality decreases with distance according to the formula ⌊q / (1 + d)⌋, the best location will typically be somewhere near the towers, where the combined signal strength is highest.

Why can we limit our search to coordinates between (0, 0) and (50, 50)? Looking at the constraints of typical problems like this, tower coordinates are usually bounded within a reasonable range (often 0 to 50). Since signal quality decreases with distance, any coordinate far outside the range where towers exist would have very weak or no signal. The optimal point must be within or very close to the region containing all towers.

The brute force approach makes sense here because:

1. The search space is relatively small - only 51 × 51 = 2,601 possible coordinates to check
2. For each coordinate, we need to calculate distances to all towers and sum up the signal qualities
3. The formula involves square roots and floor operations that don't have a simple closed-form optimization solution

Since we iterate through coordinates in order (first by x-coordinate from 0 to 50, then by y-coordinate from 0 to 50), we naturally encounter lexicographically smaller coordinates first. This means when we find a coordinate with better network quality than the current maximum, we can simply update our answer. If we later find a coordinate with the same quality, we ignore it because we already have the lexicographically smaller one.

The time complexity of O(n × m × k) where n × m is the search space (51 × 51) and k is the number of towers is acceptable given the bounded input size.

Solution Approach

The solution implements a straightforward brute force search across all possible coordinates:

1. Initialize tracking variables: We maintain mx to track the maximum network quality found so far, and ans = [0, 0] to store the coordinate with the best quality. Starting with [0, 0] ensures we have a valid answer even if all network qualities are 0.

2. Iterate through all possible coordinates: We use nested loops to check every coordinate from (0, 0) to (50, 50):

   for i in range(51):
       for j in range(51):

   This iteration order (i before j) ensures we check coordinates in lexicographic order.

3. Calculate network quality for each coordinate: For each coordinate (i, j), we:

   • Initialize a temporary sum t = 0 to accumulate the total signal quality
   • Loop through each tower [x, y, q] in the towers array
   • Calculate the Euclidean distance: d = ((x - i) ** 2 + (y - j) ** 2) ** 0.5
   • Check if the tower is reachable: if d <= radius
   • If reachable, add the signal quality to our sum: t += floor(q / (1 + d))

4. Update the best coordinate: After calculating the total network quality t for coordinate (i, j):

   if t > mx:
       mx = t
       ans = [i, j]

   We only update when we find a strictly better quality (t > mx), not when equal. This ensures that if multiple coordinates have the same quality, we keep the first one found, which is lexicographically smallest due to our iteration order.

5. Return the result: After checking all coordinates, ans contains the coordinate with maximum network quality (or the lexicographically smallest one in case of ties).

The algorithm's correctness relies on exhaustively checking all possible integral coordinates within the reasonable bounds, guaranteeing we find the global optimum.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• towers = [[1, 2, 5], [2, 1, 7], [3, 1, 9]]
• radius = 2

We need to find the coordinate with maximum network quality.

Step 1: Initialize tracking variables

• mx = 0 (maximum network quality found)
• ans = [0, 0] (best coordinate so far)

Step 2: Check some key coordinates

Let's examine a few coordinates to understand the process:

Coordinate (0, 0):

• Tower [1, 2, 5]: distance = √((1-0)² + (2-0)²) = √5 ≈ 2.24 > 2 (not reachable)
• Tower [2, 1, 7]: distance = √((2-0)² + (1-0)²) = √5 ≈ 2.24 > 2 (not reachable)
• Tower [3, 1, 9]: distance = √((3-0)² + (1-0)²) = √10 ≈ 3.16 > 2 (not reachable)
• Total network quality = 0

Coordinate (1, 1):

• Tower [1, 2, 5]: distance = √((1-1)² + (2-1)²) = 1.0 ≤ 2 (reachable)
  • Signal quality = ⌊5 / (1 + 1)⌋ = ⌊2.5⌋ = 2
• Tower [2, 1, 7]: distance = √((2-1)² + (1-1)²) = 1.0 ≤ 2 (reachable)
  • Signal quality = ⌊7 / (1 + 1)⌋ = ⌊3.5⌋ = 3
• Tower [3, 1, 9]: distance = √((3-1)² + (1-1)²) = 2.0 ≤ 2 (reachable)
  • Signal quality = ⌊9 / (1 + 2)⌋ = ⌊3.0⌋ = 3
• Total network quality = 2 + 3 + 3 = 8
• Since 8 > 0, update: mx = 8, ans = [1, 1]

Coordinate (2, 1):

• Tower [1, 2, 5]: distance = √((1-2)² + (2-1)²) = √2 ≈ 1.41 ≤ 2 (reachable)
  • Signal quality = ⌊5 / (1 + 1.41)⌋ = ⌊2.07⌋ = 2
• Tower [2, 1, 7]: distance = √((2-2)² + (1-1)²) = 0 ≤ 2 (reachable)
  • Signal quality = ⌊7 / (1 + 0)⌋ = ⌊7⌋ = 7
• Tower [3, 1, 9]: distance = √((3-2)² + (1-1)²) = 1.0 ≤ 2 (reachable)
  • Signal quality = ⌊9 / (1 + 1)⌋ = ⌊4.5⌋ = 4
• Total network quality = 2 + 7 + 4 = 13
• Since 13 > 8, update: mx = 13, ans = [2, 1]

Coordinate (2, 2):

• Tower [1, 2, 5]: distance = √((1-2)² + (2-2)²) = 1.0 ≤ 2 (reachable)
  • Signal quality = ⌊5 / (1 + 1)⌋ = ⌊2.5⌋ = 2
• Tower [2, 1, 7]: distance = √((2-2)² + (1-2)²) = 1.0 ≤ 2 (reachable)
  • Signal quality = ⌊7 / (1 + 1)⌋ = ⌊3.5⌋ = 3
• Tower [3, 1, 9]: distance = √((3-2)² + (1-2)²) = √2 ≈ 1.41 ≤ 2 (reachable)
  • Signal quality = ⌊9 / (1 + 1.41)⌋ = ⌊3.73⌋ = 3
• Total network quality = 2 + 3 + 3 = 8
• Since 8 ≤ 13, no update

Step 3: Continue checking all coordinates from (0,0) to (50,50)

After checking all 2,601 coordinates, the algorithm would find that coordinate [2, 1] has the maximum network quality of 13.

Final Result: [2, 1]

The key insights from this walkthrough:

1. Coordinates closer to towers generally have higher network quality
2. Being at distance 0 from a tower gives maximum signal from that tower (q/(1+0) = q)
3. The lexicographic ordering is automatically handled by our iteration order - we check (0,0), then (0,1), (0,2)... then (1,0), (1,1), etc.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of towers.

The code iterates through a fixed grid of 51 × 51 = 2601 positions (from coordinates [0,0] to [50,50]). For each position, it checks all towers to calculate the signal strength. Since the grid size is constant (51 × 51), and for each grid position we iterate through all n towers, the time complexity is O(51 × 51 × n) = O(2601n) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables mx (maximum signal strength), ans (answer coordinates), i, j (loop counters), t (temporary signal sum), x, y, q (tower parameters), and d (distance) are all scalar values that don't depend on the input size. No additional data structures that scale with input size are created, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Calculation or Comparison

One of the most common mistakes is incorrectly handling the distance calculation or comparison with the radius.

Pitfall Example:

# Incorrect: comparing squared distance with radius
distance_squared = (tower_x - x_coord) ** 2 + (tower_y - y_coord) ** 2
if distance_squared <= radius:  # Wrong comparison!
    total_quality += int(signal_quality / (1 + distance_squared ** 0.5))

Why it's wrong: The radius represents the actual Euclidean distance, not the squared distance. Comparing squared distance directly with radius will give incorrect results.

Correct Approach:

# Option 1: Calculate actual distance and compare
distance = ((tower_x - x_coord) ** 2 + (tower_y - y_coord) ** 2) ** 0.5
if distance <= radius:
    total_quality += int(signal_quality / (1 + distance))

# Option 2: Compare squared values (more efficient, avoids sqrt)
distance_squared = (tower_x - x_coord) ** 2 + (tower_y - y_coord) ** 2
if distance_squared <= radius * radius:
    distance = distance_squared ** 0.5
    total_quality += int(signal_quality / (1 + distance))

2. Using floor() Instead of int() for Type Conversion

The problem asks for floor division, and while math.floor() seems like the obvious choice, it can cause issues with floating-point arithmetic.

Pitfall Example:

import math
# May cause issues with floating point precision
total_quality += math.floor(signal_quality / (1 + distance))

Why it's problematic: For positive numbers, int() effectively performs floor division and is more straightforward. Using math.floor() requires an additional import and can sometimes produce unexpected results due to floating-point representation.

Better Approach:

# Simpler and works correctly for positive values
total_quality += int(signal_quality / (1 + distance))

3. Incorrect Search Bounds

Assuming the search space is too small or too large can lead to wrong answers or inefficiency.

Pitfall Example:

# Too restrictive - might miss the optimal coordinate
for x_coord in range(max(tower[0] for tower in towers) + 1):
    for y_coord in range(max(tower[1] for tower in towers) + 1):

Why it's wrong: The optimal coordinate might not be within the bounding box of tower positions. A coordinate outside the tower positions might still receive signals from multiple towers.

Correct Approach: The problem constraints typically limit coordinates to [0, 50], so checking all coordinates in this range ensures we don't miss the optimal solution:

for x_coord in range(51):  # 0 to 50 inclusive
    for y_coord in range(51):

4. Handling Ties Incorrectly

When multiple coordinates have the same maximum quality, returning the wrong one violates the lexicographic ordering requirement.

Pitfall Example:

# Wrong: using >= instead of >
if total_quality >= max_quality:  # This doesn't preserve lexicographic order!
    max_quality = total_quality
    best_coordinate = [x_coord, y_coord]

Why it's wrong: Using >= would update the answer even when qualities are equal, potentially returning a lexicographically larger coordinate.

Correct Approach:

# Only update on strictly better quality
if total_quality > max_quality:
    max_quality = total_quality
    best_coordinate = [x_coord, y_coord]

The iteration order (x from 0 to 50, then y from 0 to 50 for each x) naturally ensures lexicographic ordering when combined with strict inequality.