Skip to content

4024. Nearest Available Drone

Description

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

Solutions

Solution 1: Traversal

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 \textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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 ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments