Skip to content

3809. Best Reachable Tower

Description

You are given a 2D integer array towers, where towers[i] = [xi, yi, qi] represents the coordinates (xi, yi) and quality factor qi of the ith tower.

You are also given an integer array center = [cx, cy​​​​​​​] representing your location, and an integer radius.

A tower is reachable if its Manhattan distance from center is less than or equal to radius.

Among all reachable towers:

  • Return the coordinates of the tower with the maximum quality factor.
  • If there is a tie, return the tower with the lexicographically smallest coordinate. If no tower is reachable, return [-1, -1].

The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

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

|x| denotes the absolute value of x.

 

Example 1:

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

Output: [3,1]

Explanation:

  • Tower [1, 2, 5]: Manhattan distance = |1 - 1| + |2 - 1| = 1, reachable.
  • Tower [2, 1, 7]: Manhattan distance = |2 - 1| + |1 - 1| = 1, reachable.
  • Tower [3, 1, 9]: Manhattan distance = |3 - 1| + |1 - 1| = 2, reachable.

All towers are reachable. The maximum quality factor is 9, which corresponds to tower [3, 1].

Example 2:

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

Output: [1,3]

Explanation:

  • Tower [1, 3, 4]: Manhattan distance = |1 - 0| + |3 - 0| = 4, reachable.
  • Tower [2, 2, 4]: Manhattan distance = |2 - 0| + |2 - 0| = 4, reachable.
  • Tower [4, 4, 7]: Manhattan distance = |4 - 0| + |4 - 0| = 8, not reachable.

Among the reachable towers, the maximum quality factor is 4. Both [1, 3] and [2, 2] have the same quality, so the lexicographically smaller coordinate is [1, 3].

Example 3:

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

Output: [-1,-1]

Explanation:

  • Tower [5, 6, 8]: Manhattan distance = |5 - 1| + |6 - 2| = 8, not reachable.
  • Tower [0, 3, 5]: Manhattan distance = |0 - 1| + |3 - 2| = 2, not reachable.

No tower is reachable within the given radius, so [-1, -1] is returned.

 

Constraints:

  • 1 <= towers.length <= 105
  • towers[i] = [xi, yi, qi]
  • center = [cx, cy]
  • 0 <= xi, yi, qi, cx, cy <= 105​​​​​​​
  • 0 <= radius <= 105

Solutions

Solution 1: One-Pass Traversal

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

\[ \textit{dist} = |x_i - cx| + |y_i - cy| \]

If \(\textit{dist} > \textit{radius}\), the tower is unreachable, so we skip it. Otherwise, we compare the quality factor \(q\) of the current tower with that of the best tower:

  • If \(\textit{idx} = -1\), it means no reachable tower has been found yet, so we update \(\textit{idx}\) to the current tower's index.
  • If the current tower's quality factor \(q_i\) is greater than the best tower's quality factor \(q_{\textit{idx}}\), we update \(\textit{idx}\) to the current tower's index.
  • If the current tower's quality factor \(q_i\) is equal to the best tower's quality factor \(q_{\textit{idx}}\), we compare the coordinates of the two towers and choose the one with the smaller lexicographical order.

After the traversal ends, if \(\textit{idx} = -1\), it means there are no reachable towers, so we return \([-1, -1]\). Otherwise, we return the coordinates of the best tower.

The time complexity is \(O(n)\), where \(n\) is the number of towers. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def bestTower(
        self, towers: List[List[int]], center: List[int], radius: int
    ) -> List[int]:
        cx, cy = center
        idx = -1
        for i, (x, y, q) in enumerate(towers):
            dist = abs(x - cx) + abs(y - cy)
            if dist > radius:
                continue
            if (
                idx == -1
                or towers[idx][2] < q
                or (towers[idx][2] == q and towers[i][:2] < towers[idx][:2])
            ):
                idx = i
        return [-1, -1] if idx == -1 else towers[idx][:2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] bestTower(int[][] towers, int[] center, int radius) {
        int cx = center[0], cy = center[1];
        int idx = -1;
        for (int i = 0; i < towers.length; i++) {
            int x = towers[i][0], y = towers[i][1], q = towers[i][2];
            int dist = Math.abs(x - cx) + Math.abs(y - cy);
            if (dist > radius) {
                continue;
            }
            if (idx == -1 || towers[idx][2] < q
                || (towers[idx][2] == q
                    && (x < towers[idx][0] || (x == towers[idx][0] && y < towers[idx][1])))) {
                idx = i;
            }
        }
        return idx == -1 ? new int[] {-1, -1} : new int[] {towers[idx][0], towers[idx][1]};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> bestTower(vector<vector<int>>& towers, vector<int>& center, int radius) {
        int cx = center[0], cy = center[1];
        int idx = -1;
        for (int i = 0; i < towers.size(); ++i) {
            int x = towers[i][0], y = towers[i][1], q = towers[i][2];
            int dist = abs(x - cx) + abs(y - cy);
            if (dist > radius) {
                continue;
            }
            if (
                idx == -1
                || towers[idx][2] < q
                || (towers[idx][2] == q && (x < towers[idx][0] || (x == towers[idx][0] && y < towers[idx][1])))) {
                idx = i;
            }
        }
        if (idx == -1) {
            return {-1, -1};
        }
        return {towers[idx][0], towers[idx][1]};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func bestTower(towers [][]int, center []int, radius int) []int {
    cx, cy := center[0], center[1]
    idx := -1
    for i, a := range towers {
        x, y, q := a[0], a[1], a[2]
        dist := abs(x-cx) + abs(y-cy)
        if dist > radius {
            continue
        }
        if idx == -1 ||
            towers[idx][2] < q ||
            (towers[idx][2] == q &&
                (x < towers[idx][0] ||
                    (x == towers[idx][0] && y < towers[idx][1]))) {
            idx = i
        }
    }
    if idx == -1 {
        return []int{-1, -1}
    }
    return []int{towers[idx][0], towers[idx][1]}
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function bestTower(towers: number[][], center: number[], radius: number): number[] {
    const [cx, cy] = center;
    let idx = -1;
    for (let i = 0; i < towers.length; i++) {
        const [x, y, q] = towers[i];
        const dist = Math.abs(x - cx) + Math.abs(y - cy);
        if (dist > radius) {
            continue;
        }
        if (
            idx === -1 ||
            towers[idx][2] < q ||
            (towers[idx][2] === q &&
                (x < towers[idx][0] || (x === towers[idx][0] && y < towers[idx][1])))
        ) {
            idx = i;
        }
    }
    return idx === -1 ? [-1, -1] : [towers[idx][0], towers[idx][1]];
}

Comments