3809. Best Reachable Tower Medium

1/**
2 * [3809] Best Reachable Tower
3 *
4 * 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 i^th tower.
5 * You are also given an integer array center = [cx, cy​​​​​​​] representing your location, and an integer radius.
6 * A tower is reachable if its Manhattan distance from center is less than or equal to radius.
7 * Among all reachable towers:
8 * 
9 * 	Return the coordinates of the tower with the maximum quality factor.
10 * 	If there is a tie, return the tower with the lexicographically smallest coordinate. If no tower is reachable, return [-1, -1].
11 * The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
12 * A coordinate [xi, yi] is lexicographically smaller than [xj, yj] if xi < xj, or xi == xj and yi < yj.
13 * |x| denotes the absolute value of x.
14 *  
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">towers = [[1,2,5], [2,1,7], [3,1,9]], center = [1,1], radius = 2</span>
18 * Output: <span class="example-io">[3,1]</span>
19 * Explanation:
20 * 
21 * 	Tower [1, 2, 5]: Manhattan distance = |1 - 1| + |2 - 1| = 1, reachable.
22 * 	Tower [2, 1, 7]: Manhattan distance = |2 - 1| + |1 - 1| = 1, reachable.
23 * 	Tower [3, 1, 9]: Manhattan distance = |3 - 1| + |1 - 1| = 2, reachable.
24 * 
25 * All towers are reachable. The maximum quality factor is 9, which corresponds to tower [3, 1].
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">towers = [[1,3,4], [2,2,4], [4,4,7]], center = [0,0], radius = 5</span>
30 * Output: <span class="example-io">[1,3]</span>
31 * Explanation:
32 * 
33 * 	Tower [1, 3, 4]: Manhattan distance = |1 - 0| + |3 - 0| = 4, reachable.
34 * 	Tower [2, 2, 4]: Manhattan distance = |2 - 0| + |2 - 0| = 4, reachable.
35 * 	Tower [4, 4, 7]: Manhattan distance = |4 - 0| + |4 - 0| = 8, not reachable.
36 * 
37 * 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].
38 * </div>
39 * <strong class="example">Example 3:
40 * <div class="example-block">
41 * Input: <span class="example-io">towers = [[5,6,8], [0,3,5]], center = [1,2], radius = 1</span>
42 * Output: <span class="example-io">[-1,-1]</span>
43 * Explanation:
44 * 
45 * 	Tower [5, 6, 8]: Manhattan distance = |5 - 1| + |6 - 2| = 8, not reachable.
46 * 	Tower [0, 3, 5]: Manhattan distance = |0 - 1| + |3 - 2| = 2, not reachable.
47 * 
48 * No tower is reachable within the given radius, so [-1, -1] is returned.
49 * </div>
50 *  
51 * Constraints:
52 * 
53 * 	1 <= towers.length <= 10^5
54 * 	towers[i] = [xi, yi, qi]
55 * 	center = [cx, cy]
56 * 	0 <= xi, yi, qi, cx, cy <= 10^5​​​​​​​
57 * 	0 <= radius <= 10^5
58 * 
59 */
60pub struct Solution {}
61
62// problem: https://leetcode.com/problems/best-reachable-tower/
63// discuss: https://leetcode.com/problems/best-reachable-tower/discuss/?currentPage=1&orderBy=most_votes&query=
64
65// submission codes start here
66
67impl Solution {
68    pub fn best_tower(towers: Vec<Vec<i32>>, center: Vec<i32>, radius: i32) -> Vec<i32> {
69        vec![]
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_3809() {
81    }
82}
83