Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

Nearest Available Drone - Solution & Explanation

Easy7 min read
Practice this problem

Problem Statement

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] and target is |0 - 3| + |0 - 4| = 7, which is within its range of 8.
  • The distance between drones[1] and target is |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] and target is |2 - 5| + |1 - 5| = 7, which is greater than its range of 5.
  • The distance between drones[1] and target is |4 - 5| + |4 - 5| = 2, which is within its range of 5.
  • The distance between drones[2] and target is |6 - 5| + |6 - 5| = 2, which is within its range of 8.
  • Both drones[1] and drones[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] and target is |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 <= 100
  • drones[i] = [xi, yi, rangei]
  • target = [tx, ty]
  • -25 <= xi, yi, tx, ty <= 25
  • 1 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n)O(1)Small input or when you need a quick solution
Sort by DistanceO(n log n)O(n)When you need k nearest or precomputed order
Linear Scan with Tie-BreakingO(n)O(1)General case, single query, memory constrained

Video Solution

Nearest Available Drone | LeetCode 4024 | Weekly Contest 515 | Java | Developer Coder • Developer Coder • 82 views views

Watch 2 more video solutions →

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.

Ready to solve this problem?

Practice Nearest Available Drone with our built-in code editor and test cases.

Practice on FleetCode