Nearest Available Drone - Video Solutions

Problem Overview: You are given a set of drones with coordinates and a customer location. The task is to find the drone closest to the customer, i.e., the one with the minimum Euclidean distance. If multiple drones are equidistant, return the one with the smallest ID.

Approach 1: Brute Force (O(n) time, O(1) space)

Iterate through the list of drones, compute the squared distance to the customer for each, and keep track of the minimum distance and the corresponding drone ID. Use squared distance to avoid floating-point precision issues. This approach is straightforward and works perfectly for small inputs, but it doesn't scale well if the list is huge and you need repeated queries.

Approach 2: Sort by Distance (O(n log n) time, O(n) space)

Create an array of pairs (distance, ID) and sort it by distance, then by ID. The first element after sorting is the answer. This is useful if you need the k nearest drones or if the list is static and you want to precompute an ordering. However, it is overkill for a single query and uses extra memory.

Approach 3: Linear Scan with Tie-Breaking (O(n) time, O(1) space) - Optimal

The optimal solution is a single pass that tracks the best (minimum distance, smallest ID) pair. For each drone, compute the squared distance, and if it's less than the current minimum, update. If it's equal, update only if the ID is smaller. This avoids sorting and uses constant extra space. It's the most efficient for a single query and is what interviewers expect.

Recommended for interviews: The linear scan with tie-breaking is the expected solution. It shows you can optimize a simple problem and handle edge cases like ties. Brute force is acceptable as a starting point, but you should quickly move to the O(n) approach. The problem is tagged General, so it tests basic iteration and comparison logic.