Tap here to switch tabs
Problem
Submissions

Problem: Best Reachable Tower

Best Reachable Tower asks you to choose among towers within a center's Manhattan radius, returning highest-quality coordinates, with lexicographically smallest ties, or sentinel pair if none qualify.

Statement

You are given a 22D integer array towers where each towers[i] = [xi,yi,qi][x_i, y_i, q_i] denotes a tower located at coordinates (xi,yi)(x_i, y_i) with a quality factor qiq_i. You are also given an integer array center = [cx,cy][cx, cy] representing a location and an integer radius.

A tower is considered reachable if the Manhattan distance between (xi,yi)(x_i, y_i) and (cx,cy)(cx, cy) is at most radius. The Manhattan distance between two points (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) is ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|.

Return an integer array [x,y][x, y] representing the coordinates of the reachable 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][ -1, -1 ].

Note: A coordinate [x1,y1][x_1, y_1] is lexicographically smaller than [x2,y2][x_2, y_2] if x1<x2x_1 < x_2, or if x1=x2x_1 = x_2 and y1<y2y_1 < y_2.

Constraints:

  • 1≤1 \leq towers.length ≤105\leq 10^5

  • towers[i] = [xi,yi,qi][x_i, y_i, q_i]

  • center = [cx,cy][cx, cy]

  • 0≤xi,yi,qi,cx,cy≤1050 \leq x_i, y_i, q_i, cx, cy \leq 10^5

  • 0≤0 \leq radius ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Best Reachable Tower

Best Reachable Tower asks you to choose among towers within a center's Manhattan radius, returning highest-quality coordinates, with lexicographically smallest ties, or sentinel pair if none qualify.

Statement

You are given a 22D integer array towers where each towers[i] = [xi,yi,qi][x_i, y_i, q_i] denotes a tower located at coordinates (xi,yi)(x_i, y_i) with a quality factor qiq_i. You are also given an integer array center = [cx,cy][cx, cy] representing a location and an integer radius.

A tower is considered reachable if the Manhattan distance between (xi,yi)(x_i, y_i) and (cx,cy)(cx, cy) is at most radius. The Manhattan distance between two points (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) is ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|.

Return an integer array [x,y][x, y] representing the coordinates of the reachable 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][ -1, -1 ].

Note: A coordinate [x1,y1][x_1, y_1] is lexicographically smaller than [x2,y2][x_2, y_2] if x1<x2x_1 < x_2, or if x1=x2x_1 = x_2 and y1<y2y_1 < y_2.

Constraints:

  • 1≤1 \leq towers.length ≤105\leq 10^5

  • towers[i] = [xi,yi,qi][x_i, y_i, q_i]

  • center = [cx,cy][cx, cy]

  • 0≤xi,yi,qi,cx,cy≤1050 \leq x_i, y_i, q_i, cx, cy \leq 10^5

  • 0≤0 \leq radius ≤105\leq 10^5