How do you solve Best Reachable Tower on LeetCode?

Best Reachable Tower (LeetCode #3809) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding Manhattan distance is crucial.

What is the time complexity of Best Reachable Tower?

The optimal solution for Best Reachable Tower runs in O(n) time and uses O(1) space. We only traverse the list of towers once, making the time complexity linear.

What is the brute force solution for Best Reachable Tower?

The brute force approach for Best Reachable Tower is Brute Force, with O(n) time complexity and O(1) space complexity. We check each tower's distance from the center and keep track of the one with the highest quality. If distances are equal, we choose the lexicographically smaller coordinate. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Best Reachable Tower?

Best Reachable Tower uses the following concepts: Array. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Best Reachable Tower?

Clarify the problem requirements. Discuss edge cases like no reachable towers. Explain your thought process while coding.

What are common mistakes when solving Best Reachable Tower?

Ignoring the lexicographical order in ties. Not correctly calculating the Manhattan distance.

#3809

Best Reachable Tower

Medium

ArrayHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

We can efficiently find the best tower by iterating through the list once, checking distances and updating the best tower based on quality and coordinates.

⚙️

Algorithm

3 steps

1Step 1: Initialize best tower coordinates and max quality.
2Step 2: Loop through each tower, compute Manhattan distance.
3Step 3: Update best tower if it's reachable and has higher quality or is lexicographically smaller.

solution.py10 lines

1def bestReachableTower(towers, center, radius):
2    best = [-1, -1]
3    max_quality = -1
4    for x, y, q in towers:
5        dist = abs(x - center[0]) + abs(y - center[1])
6        if dist <= radius:
7            if q > max_quality or (q == max_quality and (best[0] == -1 or (x < best[0] or (x == best[0] and y < best[1])))):
8                best = [x, y]
9                max_quality = q
10    return best

ℹ

Complexity note: We only traverse the list of towers once, making the time complexity linear.

1Understanding Manhattan distance is crucial.
2Quality and coordinates must be compared correctly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.