3809. Best Reachable Tower

MediumArray

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 2D integer array towers, where each element towers[i] = [xi, yi, qi] describes the i-th tower. Here (xi, yi) are the tower's coordinates, and qi is its quality factor.

You are also given:

An integer array center = [cx, cy] representing your own location.
An integer radius representing how far you can reach.

Your task is to look at all the reachable towers and:

Return the coordinates [x, y] of the tower with the maximum quality factor.
If multiple reachable towers share the same maximum quality factor, return the one with the lexicographically smallest coordinate.
If no tower is reachable, return [-1, -1].

A coordinate [xi, yi] is lexicographically smaller than [xj, yj] if xi < xj, or if xi == xj and yi < yj.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Scanning all towers to find the reachable one with maximum quality factor and ties broken by coordinates is a straightforward enumeration.

Open in Flowchart

Intuition

The problem asks us to find a single "best" tower among all reachable ones, based on a clear ranking rule. Whenever we need to pick the single best item out of a collection according to some comparison criteria, a natural approach is to simply scan through every item once and keep track of the best one seen so far.

Let's break down what "best" means here. We are comparing towers using two layers of priority:

Reachability first — only towers whose Manhattan distance |xi - cx| + |yi - cy| is at most radius are even candidates. Any tower failing this check can be ignored immediately.
Higher quality factor — among reachable towers, the one with the larger q wins.
Lexicographically smaller coordinate — if two towers tie on quality, the one with the smaller [x, y] coordinate wins.

Since the constraints involve checking each tower independently (a tower's eligibility doesn't depend on the others), there's no need for sorting or any complex data structure. We can determine the answer in a single pass.

The idea is to keep a variable idx that remembers the index of the best tower found so far, starting at -1 to indicate "nothing found yet." As we walk through each tower, we:

Skip it if it's unreachable.
Otherwise, compare it against our current best. We update our best if any of these hold:
- idx == -1 (we haven't found any reachable tower yet, so this one is automatically the best),
- the current tower's quality q is strictly greater than the best so far,
- the qualities are equal but the current tower's coordinate is lexicographically smaller.

By chaining these conditions together, each tower is correctly compared and the best one naturally "bubbles up" by the end of the loop. After the scan, if idx is still -1, no tower was reachable, so we return [-1, -1]; otherwise, we return the stored best tower's coordinates. This gives us a clean O(n) solution with O(1) extra space.

Solution Approach

Solution 1: One-Pass Traversal

We define a variable idx to record the index of the current best tower, initially idx = -1. Then, we traverse each tower and calculate the Manhattan distance dist between it and center:

dist = |xi - cx| + |yi - cy|

If dist > radius, the tower is unreachable, so we skip it with continue. Otherwise, we compare the current tower against the best tower found so far using the following conditions, joined together with or:

If idx == -1, it means no reachable tower has been found yet, so we update idx to the current tower's index.
If the current tower's quality factor q is greater than the best tower's quality factor towers[idx][2], we update idx to the current tower's index.
If the current tower's quality factor q is equal to the best tower's quality factor towers[idx][2], we compare the coordinates of the two towers using towers[i][:2] < towers[idx][:2] and choose the one with the smaller lexicographical order.

In Python, the slice towers[i][:2] extracts the [x, y] coordinate of the tower, and comparing two lists with < performs a natural lexicographical comparison — first by the x value, then by the y value. This conveniently handles the tie-breaking rule without writing extra logic.

After the traversal ends, if idx == -1, it means there are no reachable towers, so we return [-1, -1]. Otherwise, we return towers[idx][:2], the coordinates of the best tower.

The time complexity is O(n), where n is the number of towers, since we visit each tower exactly once. The space complexity is O(1), as we only use a single index variable to track the best result.

Example Walkthrough

Let's trace through a small concrete example to see how the one-pass traversal works.

Input:

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

We initialize idx = -1 (no best tower found yet) and scan the towers one by one.

Tower 0: [1, 2, 5]

Manhattan distance: |1 - 2| + |2 - 2| = 1 + 0 = 1
1 ≤ 3, so it's reachable.
Since idx == -1 (nothing found yet), this tower becomes our best.
Update idx = 0. Best so far: quality 5 at [1, 2].

Tower 1: [3, 1, 7]

Manhattan distance: |3 - 2| + |1 - 2| = 1 + 1 = 2
2 ≤ 3, so it's reachable.
Compare quality: current q = 7 vs best towers[0][2] = 5. Since 7 > 5, this tower is better.
Update idx = 1. Best so far: quality 7 at [3, 1].

Tower 2: [4, 5, 7]

Manhattan distance: |4 - 2| + |5 - 2| = 2 + 3 = 5
5 > 3, so it's unreachable. We continue and skip it.
Best remains: quality 7 at [3, 1].

Note: even though this tower ties the best quality of 7, it never gets considered because it fails the reachability check first — illustrating that reachability is the top priority.

Tower 3: [2, 3, 9]

Manhattan distance: |2 - 2| + |3 - 2| = 0 + 1 = 1
1 ≤ 3, so it's reachable.
Compare quality: current q = 9 vs best towers[1][2] = 7. Since 9 > 7, this tower is better.
Update idx = 3. Best so far: quality 9 at [2, 3].

After the scan: idx = 3, which is not -1, so we return the coordinates of the best tower:

Output: towers[3][:2] = [2, 3]

Tie-breaking illustration: Suppose Tower 3 had been [2, 3, 7] instead (same quality as the best). When comparing, 7 == 7, so we'd fall to the coordinate check: towers[3][:2] = [2, 3] vs towers[1][:2] = [3, 1]. Since [2, 3] < [3, 1] lexicographically (because 2 < 3), Tower 3 would still win. This shows how the lexicographically smallest coordinate rule breaks ties, handled cleanly by Python's list comparison.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def bestTower(
6        self, towers: List[List[int]], center: List[int], radius: int
7    ) -> List[int]:
8        center_x, center_y = center
9
10        # Index of the current best tower; -1 means none found yet.
11        best_index = -1
12
13        for i, (x, y, quality) in enumerate(towers):
14            # Use Manhattan distance to measure reach from the center.
15            distance = abs(x - center_x) + abs(y - center_y)
16
17            # Skip towers that lie outside the allowed radius.
18            if distance > radius:
19                continue
20
21            if best_index == -1:
22                # First valid tower found, take it as the current best.
23                best_index = i
24                continue
25
26            best_quality = towers[best_index][2]
27            best_coord = towers[best_index][:2]
28            current_coord = [x, y]
29
30            # Prefer a strictly higher quality; on equal quality,
31            # prefer the lexicographically smaller coordinate.
32            if quality > best_quality or (
33                quality == best_quality and current_coord < best_coord
34            ):
35                best_index = i
36
37        # Return the best tower's coordinates, or [-1, -1] if none qualified.
38        return [-1, -1] if best_index == -1 else towers[best_index][:2]
39

1class Solution {
2    public int[] bestTower(int[][] towers, int[] center, int radius) {
3        // Coordinates of the center point
4        int centerX = center[0];
5        int centerY = center[1];
6
7        // Index of the best tower found so far (-1 means none yet)
8        int bestIndex = -1;
9
10        // Iterate over every tower to find the best candidate
11        for (int i = 0; i < towers.length; i++) {
12            int towerX = towers[i][0];
13            int towerY = towers[i][1];
14            int quality = towers[i][2];
15
16            // Use Manhattan distance from the tower to the center
17            int distance = Math.abs(towerX - centerX) + Math.abs(towerY - centerY);
18
19            // Skip towers that lie outside the allowed radius
20            if (distance > radius) {
21                continue;
22            }
23
24            // Update the best tower if:
25            // 1. No valid tower has been chosen yet, OR
26            // 2. The current tower has higher quality, OR
27            // 3. Quality ties, but the current tower has a smaller coordinate
28            //    (smaller x, or equal x with smaller y) for tie-breaking
29            boolean isFirstCandidate = (bestIndex == -1);
30            boolean hasHigherQuality = !isFirstCandidate && towers[bestIndex][2] < quality;
31            boolean isBetterTieBreak = !isFirstCandidate
32                    && towers[bestIndex][2] == quality
33                    && (towerX < towers[bestIndex][0]
34                        || (towerX == towers[bestIndex][0] && towerY < towers[bestIndex][1]));
35
36            if (isFirstCandidate || hasHigherQuality || isBetterTieBreak) {
37                bestIndex = i;
38            }
39        }
40
41        // Return the coordinates of the best tower, or {-1, -1} if none qualifies
42        return bestIndex == -1
43                ? new int[] {-1, -1}
44                : new int[] {towers[bestIndex][0], towers[bestIndex][1]};
45    }
46}
47

1class Solution {
2public:
3    vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
4        // Center coordinates we measure distance from.
5        const int center_x = center[0];
6        const int center_y = center[1];
7
8        // Index of the best tower found so far (-1 means none yet).
9        int best_index = -1;
10
11        for (int i = 0; i < static_cast<int>(towers.size()); ++i) {
12            const int x = towers[i][0];       // tower x-coordinate
13            const int y = towers[i][1];       // tower y-coordinate
14            const int quality = towers[i][2]; // tower quality/signal
15
16            // Manhattan distance from the tower to the center.
17            const int distance = abs(x - center_x) + abs(y - center_y);
18
19            // Skip towers outside the allowed radius.
20            if (distance > radius) {
21                continue;
22            }
23
24            // Update the best tower when:
25            //  - no tower has been chosen yet, OR
26            //  - this tower has strictly higher quality, OR
27            //  - equal quality but smaller coordinate (x first, then y).
28            const bool no_candidate = (best_index == -1);
29            const bool higher_quality =
30                !no_candidate && towers[best_index][2] < quality;
31            const bool equal_quality_smaller_coord =
32                !no_candidate &&
33                towers[best_index][2] == quality &&
34                (x < towers[best_index][0] ||
35                 (x == towers[best_index][0] && y < towers[best_index][1]));
36
37            if (no_candidate || higher_quality || equal_quality_smaller_coord) {
38                best_index = i;
39            }
40        }
41
42        // No tower lies within the radius.
43        if (best_index == -1) {
44            return {-1, -1};
45        }
46
47        // Return the coordinates of the best tower.
48        return {towers[best_index][0], towers[best_index][1]};
49    }
50};
51

1/**
2 * Finds the coordinates of the best tower located within a given Manhattan-distance radius from a center point.
3 *
4 * Selection priority:
5 *   1. Highest signal quality (q).
6 *   2. On equal quality, the smaller x coordinate.
7 *   3. On equal quality and x, the smaller y coordinate.
8 *
9 * @param towers - List of towers, each represented as [x, y, quality].
10 * @param center - The center point as [centerX, centerY].
11 * @param radius - The maximum allowed Manhattan distance from the center.
12 * @returns The [x, y] of the best tower, or [-1, -1] if none lies within the radius.
13 */
14function bestTower(towers: number[][], center: number[], radius: number): number[] {
15    const [centerX, centerY] = center;
16
17    // Index of the currently selected best tower; -1 means none found yet.
18    let bestIndex = -1;
19
20    for (let i = 0; i < towers.length; i++) {
21        const [x, y, quality] = towers[i];
22
23        // Manhattan distance from the current tower to the center.
24        const distance = Math.abs(x - centerX) + Math.abs(y - centerY);
25
26        // Skip towers outside the coverage radius.
27        if (distance > radius) {
28            continue;
29        }
30
31        // Decide whether the current tower is better than the stored best.
32        if (bestIndex === -1) {
33            // First valid tower found.
34            bestIndex = i;
35            continue;
36        }
37
38        const [bestX, bestY, bestQuality] = towers[bestIndex];
39
40        if (
41            // Higher quality wins outright.
42            bestQuality < quality ||
43            // On equal quality, prefer smaller x, then smaller y.
44            (bestQuality === quality &&
45                (x < bestX || (x === bestX && y < bestY)))
46        ) {
47            bestIndex = i;
48        }
49    }
50
51    // Return the best tower's coordinates, or [-1, -1] if no tower qualified.
52    return bestIndex === -1 ? [-1, -1] : [towers[bestIndex][0], towers[bestIndex][1]];
53}
54

Time and Space Complexity

Time Complexity: O(n), where n is the number of towers. The code iterates through the towers list exactly once with a single for loop. For each tower, it performs a constant amount of work—computing the Manhattan distance abs(x - cx) + abs(y - cy), comparing it against radius, and evaluating the candidate conditions to update idx. Each of these operations takes O(1) time, so the total time is O(n).
Space Complexity: O(1). The algorithm only uses a fixed number of auxiliary variables (cx, cy, idx, dist, and the loop variables i, x, y, q), regardless of the input size. No additional data structures that grow with the input are allocated, so the extra space used is constant.

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

Common Pitfalls

Pitfall 1: Using `<` instead of `<=` for the Manhattan distance check

A frequent mistake is treating the radius boundary as exclusive rather than inclusive. The problem states a tower is reachable when its Manhattan distance is less than or equal to radius. Writing the skip condition as distance >= radius (or the reachable check as distance < radius) wrongly excludes towers sitting exactly on the boundary.

Wrong:

if distance >= radius:  # incorrectly drops towers exactly on the edge
    continue

Correct:

if distance > radius:   # only drop towers strictly outside the radius
    continue

Pitfall 2: Forgetting the lexicographic tie-break on equal quality

Some implementations only keep the first tower seen with the maximum quality, ignoring the requirement to return the lexicographically smallest coordinate. Because towers are visited in input order (not sorted by coordinate), the first one encountered may not be the smallest.

Wrong:

if quality > best_quality:   # ties resolved by input order, not coordinate
    best_index = i

Correct:

if quality > best_quality or (
    quality == best_quality and current_coord < best_coord
):
    best_index = i

Pitfall 3: Comparing the full tower list instead of just the coordinates

When breaking ties, comparing towers[i] < towers[best_index] compares the entire [x, y, q] triple. Since the qualities are already equal in the tie-break branch, this happens to work here, but it becomes misleading and error-prone if the comparison logic is ever reused or reordered. Always slice to [:2] so the comparison is explicitly about coordinates only.

Risky:

if towers[i] < towers[best_index]:   # compares x, then y, then quality
    best_index = i

Clear and correct:

if towers[i][:2] < towers[best_index][:2]:   # compares only x then y
    best_index = i

Pitfall 4: Mishandling the "no reachable tower" case

If you initialize the result to the first tower in the array without verifying it is reachable, you may return a coordinate even when no tower lies within the radius. The best_index == -1 sentinel must be checked at the end so that an empty reachable set correctly returns [-1, -1].

Wrong:

best_index = 0          # assumes towers[0] is reachable
...
return towers[best_index][:2]   # may return an unreachable tower

Correct:

best_index = -1         # no tower assumed reachable initially
...
return [-1, -1] if best_index == -1 else towers[best_index][:2]

Pitfall 5: Integer overflow in other languages

While Python handles arbitrarily large integers natively, porting this solution to languages like Java or C++ requires care: the sum abs(x - cx) + abs(y - cy) can overflow a 32-bit int when coordinates are large. Use a 64-bit type (long) for the distance computation in those languages to stay safe.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering

3809. Best Reachable Tower

Problem Description

How We Pick the Algorithm

Why Simulation / Basic DSA?

Intuition

Solution Approach

Solution 1: One-Pass Traversal

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Using < instead of <= for the Manhattan distance check

Pitfall 2: Forgetting the lexicographic tie-break on equal quality

Pitfall 3: Comparing the full tower list instead of just the coordinates

Pitfall 4: Mishandling the "no reachable tower" case

Pitfall 5: Integer overflow in other languages

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 1: Using `<` instead of `<=` for the Manhattan distance check