LeetCode 3809 - Best Reachable Tower

This problem asks us to identify the "best reachable tower" from a given center location within a specified Manhattan distance radius. Each tower has a coordinate (xi, yi) and a quality factor qi.

leetcodemediumarray

LeetCode Problem 3809

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

This problem asks us to identify the "best reachable tower" from a given center location within a specified Manhattan distance radius. Each tower has a coordinate (xi, yi) and a quality factor qi. A tower is considered reachable if its Manhattan distance from the center (cx, cy) is less than or equal to the given radius. Among all reachable towers, we are asked to select the one with the maximum quality factor. If multiple towers share the maximum quality, the tie is broken by selecting the lexicographically smallest coordinate. If no tower is reachable, we return [-1, -1].

The inputs consist of a list of towers, each represented as [xi, yi, qi], a center [cx, cy], and an integer radius. The constraints indicate that the number of towers can be large (up to 100,000), and the coordinates and quality factors can also be as large as 100,000. This tells us that our solution must be linear or nearly linear, and we should avoid nested loops over all possible positions.

Important edge cases include when no towers are reachable, when multiple towers have the same maximum quality factor, and when towers are located exactly at the Manhattan distance boundary. The problem guarantees valid input ranges, so negative coordinates are not a concern.

Approaches

A brute-force approach would iterate through every tower, compute its Manhattan distance from the center, and check whether it is within the radius. For reachable towers, we would track the maximum quality factor and, in the case of ties, compare coordinates lexicographically. This approach is simple and correct because it examines all towers, but it is already optimal in time complexity for this problem since we must inspect each tower at least once. There is no faster method because the data is unsorted, and any solution must evaluate the distance and quality of every tower.

The key observation is that the problem reduces to a single pass through the array: for each tower, compute its Manhattan distance, check if it is reachable, and update a running best tower based on quality and lexicographic ordering. No additional data structures are required, so space complexity is constant.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Single pass checking reachability and maintaining maximum
Optimal O(n) O(1) Same as brute force; no sorting or extra structures needed

Algorithm Walkthrough

  1. Initialize a variable best_tower as [-1, -1] to store the current best tower coordinates, and max_quality as -1 to track the highest quality seen among reachable towers.
  2. Iterate over each tower [xi, yi, qi] in the towers array.
  3. Compute the Manhattan distance from the center as abs(xi - cx) + abs(yi - cy). This tells us if the tower is reachable.
  4. If the distance is less than or equal to the radius, the tower is reachable. Compare its quality qi with max_quality.
  5. If qi is greater than max_quality, update max_quality to qi and best_tower to [xi, yi].
  6. If qi equals max_quality, check if [xi, yi] is lexicographically smaller than best_tower. If it is, update best_tower to [xi, yi].
  7. After processing all towers, return best_tower.

Why it works: The algorithm maintains the invariant that best_tower always contains the coordinates of the highest-quality reachable tower encountered so far, with lexicographic tie-breaking. Since every tower is examined exactly once, we are guaranteed to find the correct answer.

Python Solution

from typing import List

class Solution:
    def bestTower(self, towers: List[List[int]], center: List[int], radius: int) -> List[int]:
        cx, cy = center
        best_tower = [-1, -1]
        max_quality = -1
        
        for x, y, q in towers:
            manhattan_distance = abs(x - cx) + abs(y - cy)
            if manhattan_distance <= radius:
                if q > max_quality or (q == max_quality and [x, y] < best_tower):
                    max_quality = q
                    best_tower = [x, y]
        
        return best_tower

In the implementation, we unpack the center coordinates into cx and cy. For each tower, we compute the Manhattan distance and check if it is reachable. If it is, we use a combined condition to decide whether to update best_tower: either the tower has a higher quality or ties in quality but is lexicographically smaller. Finally, we return the result.

Go Solution

func bestTower(towers [][]int, center []int, radius int) []int {
    cx, cy := center[0], center[1]
    bestTower := []int{-1, -1}
    maxQuality := -1

    for _, tower := range towers {
        x, y, q := tower[0], tower[1], tower[2]
        manhattan := abs(x-cx) + abs(y-cy)
        if manhattan <= radius {
            if q > maxQuality || (q == maxQuality && (x < bestTower[0] || (x == bestTower[0] && y < bestTower[1]))) {
                maxQuality = q
                bestTower[0] = x
                bestTower[1] = y
            }
        }
    }
    return bestTower
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

In Go, we manually define an abs function for integer absolute value. Lexicographic comparison is done with explicit checks on x and y because Go slices do not support direct comparison. Otherwise, the logic mirrors the Python implementation.

Worked Examples

Example 1

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

Tower Manhattan Distance Reachable? max_quality best_tower
[1,2,5] 1 Yes 5 [1,2]
[2,1,7] 1 Yes 7 [2,1]
[3,1,9] 2 Yes 9 [3,1]

Output: [3,1]

Example 2

Input: towers = [[1,3,4], [2,2,4], [4,4,7]], center = [0,0], radius = 5

Tower Manhattan Distance Reachable? max_quality best_tower
[1,3,4] 4 Yes 4 [1,3]
[2,2,4] 4 Yes 4 [1,3] (lex smaller)
[4,4,7] 8 No 4 [1,3]

Output: [1,3]

Example 3

Input: towers = [[5,6,8], [0,3,5]], center = [1,2], radius = 1

All towers are out of reach. Output: [-1,-1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each tower is visited exactly once and distance calculation is O(1)
Space O(1) Only a few variables are used to track best tower and maximum quality

The solution is linear in the number of towers, which is optimal since we must inspect each tower at least once.

Test Cases

sol = Solution()

# Provided examples
assert sol.bestTower([[1,2,5], [2,1,7], [3,1,9]], [1,1], 2) == [3,1]  # maximum quality tower
assert sol.bestTower([[1,3,4], [2,2,4], [4,4,7]], [0,0], 5) == [1,3]  # tie-breaking lexicographically
assert sol.bestTower([[5,6,8], [0,3,5]], [1,2], 1) == [-1,-1]        # no reachable towers

# Edge case: only one tower reachable
assert sol.bestTower([[0,0,1]], [0,0], 0) == [0,0]

# Edge case: multiple towers same quality at same distance
assert sol.bestTower([[1,1,5], [1,2,5], [2,1,5]], [0,0], 3) == [1,1]

# Edge case: large radius includes all
assert sol.bestTower([[100000,100000,1]], [0,0], 200000) == [100000,100000]

# Edge case: zero radius, only exact center reachable
assert sol.bestTower([[1,1,10], [0,0,5]], [0,0], 0) == [0,0