Nearest Available Drone solution and explanation
2 more videos on this problem
The problem
You are given a 2D integer array drones, where drones[i] = [xi, yi, rangei] represents the x-coordinate, y-coordinate, and travel range of the ith drone.
You are also given an integer array target = [tx, ty], representing the coordinates of the target.
A drone drones[i] can reach the target if the Manhattan distance between its coordinates and the target coordinates is less than or equal to its rangei.
Return the index of the reachable drone with the minimum Manhattan distance to the target. If there is a tie, return the smallest index. If no drone can reach the target, return -1.
Example 1:
Input: drones = [[0,0,8],[2,2,9]], target = [3,4]
Output: 1
Explanation:
- The distance between
drones[0]andtargetis|0 - 3| + |0 - 4| = 7, which is within its range of 8. - The distance between
drones[1]andtargetis|2 - 3| + |2 - 4| = 3, which is within its range of 9. - Since
drones[1]is the nearest drone, the answer is 1.
Example 2:
Input: drones = [[2,1,5],[4,4,5],[6,6,8]], target = [5,5]
Output: 1
Explanation:
- The distance between
drones[0]andtargetis|2 - 5| + |1 - 5| = 7, which is greater than its range of 5. - The distance between
drones[1]andtargetis|4 - 5| + |4 - 5| = 2, which is within its range of 5. - The distance between
drones[2]andtargetis|6 - 5| + |6 - 5| = 2, which is within its range of 8. - Both
drones[1]anddrones[2]are the nearest drones. Since we should return the smallest index, the answer is 1.
Example 3:
Input: drones = [[4,4,5]], target = [8,6]
Output: -1
Explanation:
- The distance between
drones[0]andtargetis|4 - 8| + |4 - 6| = 6, which is greater than its range of 5. - No drone can reach the target, so the answer is -1.
Constraints:
1 <= drones.length <= 100drones[i] = [xi, yi, rangei]target = [tx, ty]-25 <= xi, yi, tx, ty <= 251 <= rangei <= 100
Approach overview
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.
Solution
We iterate through each drone and compute the Manhattan distance d = |x_i - t_x| + |y_i - t_y| to the target. If d \le range_i, the drone can reach the target. Among all reachable drones, we choose the one with the minimum distance. If there is a tie, we keep the smaller index because we scan from left to right and only update when the distance is strictly smaller. If no drone can reach the target, return -1.
The time complexity is O(n), and the space complexity is O(1), where n is the number of drones.
class Solution:
def nearestDrone(self, drones: list[list[int]], target: list[int]) -> int:
ans = -1
mn = inf
tx, ty = target
for i, (x, y, r) in enumerate(drones):
d = abs(x - tx) + abs(y - ty)
if d <= r and mn > d:
ans = i
mn = d
return ansclass Solution {
public int nearestDrone(int[][] drones, int[] target) {
int ans = -1;
int mn = Integer.MAX_VALUE;
int tx = target[0], ty = target[1];
for (int i = 0; i < drones.length; i++) {
int x = drones[i][0];
int y = drones[i][1];
int r = drones[i][2];
int d = Math.abs(x - tx) + Math.abs(y - ty);
if (d <= r && mn > d) {
ans = i;
mn = d;
}
}
return ans;
}
}class Solution {
public:
int nearestDrone(vector<vector<int>>& drones, vector<int>& target) {
int ans = -1;
int mn = INT_MAX;
int tx = target[0], ty = target[1];
for (int i = 0; i < drones.size(); i++) {
int x = drones[i][0];
int y = drones[i][1];
int r = drones[i][2];
int d = abs(x - tx) + abs(y - ty);
if (d <= r && mn > d) {
ans = i;
mn = d;
}
}
return ans;
}
};function nearestDrone(drones: number[][], target: number[]): number {
let ans = -1;
let mn = Infinity;
const [tx, ty] = target;
for (let i = 0; i < drones.length; i++) {
const [x, y, r] = drones[i];
const d = Math.abs(x - tx) + Math.abs(y - ty);
if (d <= r && mn > d) {
ans = i;
mn = d;
}
}
return ans;
}func nearestDrone(drones [][]int, target []int) int {
ans := -1
mn := math.MaxInt32
tx, ty := target[0], target[1]
for i, drone := range drones {
x, y, r := drone[0], drone[1], drone[2]
d := abs(x-tx) + abs(y-ty)
if d <= r && mn > d {
ans = i
mn = d
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Small input or when you need a quick solution |
| Sort by Distance | O(n log n) | O(n) | When you need k nearest or precomputed order |
| Linear Scan with Tie-Breaking | O(n) | O(1) | General case, single query, memory constrained |
Frequently asked questions
Is Nearest Available Drone easy or hard?
It is rated Easy with a 66.2% acceptance rate. The problem is straightforward and focuses on basic array traversal and comparison logic.
Nearest Available Drone Python/Java solution
In Python, you can use a loop with a tuple comparison. In Java, use a for-each loop and Math.pow or custom squared distance. Both solutions run in O(n) time and O(1) space.
How to solve Nearest Available Drone in O(n)?
Iterate through each drone, compute the squared distance to the customer, and maintain a variable for the minimum distance and the corresponding drone ID. If a drone has a smaller distance, update; if equal, update only if the ID is smaller.
What is the best approach for Nearest Available Drone?
The best approach is a linear scan that computes the squared distance for each drone and tracks the minimum distance with the smallest ID. It runs in O(n) time and O(1) space, making it optimal for a single query.
Is Nearest Available Drone asked at Google/Amazon/Meta?
This problem is tagged as General and is a common warm-up question in interviews at top tech companies. It tests basic iteration and comparison skills, so it may appear as an easy round question.
What data structure is used in Nearest Available Drone?
No complex data structure is needed. The optimal solution uses simple variables to track the minimum distance and ID. Sorting approaches use an array of pairs, but that's not necessary for the optimal solution.
What is the time complexity of Nearest Available Drone?
The optimal solution runs in O(n) time, where n is the number of drones. The brute force also runs in O(n) but with a simpler implementation. Sorting-based approaches take O(n log n) time.