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:
[-1, -1].(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:
[1, 2, 5]: Manhattan distance = |1 - 1| + |2 - 1| = 1, reachable.[2, 1, 7]: Manhattan distance = |2 - 1| + |1 - 1| = 1, reachable.[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:
[1, 3, 4]: Manhattan distance = |1 - 0| + |3 - 0| = 4, reachable.[2, 2, 4]: Manhattan distance = |2 - 0| + |2 - 0| = 4, reachable.[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:
[5, 6, 8]: Manhattan distance = |5 - 1| + |6 - 2| = 8, not reachable.[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 <= 105Loading editor...
[[1,2,5],[2,1,7],[3,1,9]] [1,1] 2