Welcome to Subscribe On Youtube
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 <= 105towers[i] = [xi, yi, qi]center = [cx, cy]0 <= xi, yi, qi, cx, cy <= 1050 <= 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)$.
-
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]}; } } -
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]}; } }; -
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] -
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 } -
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]]; }