Max distance

In the city, there are N districts (numbered from 0 to N-1) connected with M streets. The connections are described by two arrays, A and B, both of length M. A pair (A[K], B[K]) marks a street between districts A[K] and B[K] (for K from 0 to M-1). There are also L hospitals whose locations are described by an array H. The J-th hospital is placed in district H[J] (for J from 0 to L-1).

If an ambulance is needed in a district, one is sent from the hospital from which it will arrive in the shortest time. The ambulance arrives by the shortest possible route; passing one street takes exactly 1 minute.

Potentially, there might be a patient in need in any district of the city. What is the longest time required to reach any possible patient with an ambulance?

If some district cannot be reached with an ambulance, the function should return -1.

Examples

Example 1:

N = 6
A = [0, 1, 1, 3, 0]
B = [1, 2, 3, 4, 5]
H = [2, 4]
Output: 3

• Explanation: District 5 has the longest waiting time. The ambulance will arrive from the hospital in district 2 in three minutes via route 2 → 1 → 0 → 5.

---

Example 2:

N = 6
A = [0, 1, 1, 3, 0, 4]
B = [1, 2, 3, 4, 5, 5]
H = [2, 4]
Output: 2

---

Example 3:

N = 6
A = [0, 1, 1, 3]
B = [1, 2, 3, 4]
H = [2, 4]
Output: -1

• Explanation: District 5 is not connected with any district that has a hospital.

---

Example 4:

N = 3
A = [1]
B = [2]
H = [0, 1, 2]
Output: 0

• Explanation: There is a hospital in every district.

---

Constraints

• N is an integer within the range [1..100,000].

• M is an integer within the range [0..100,000].

• L is an integer within the range [1..N].

• The elements of H are all distinct.

• Each element of arrays A, B, and H is an integer within the range [0..N-1].

• Every street goes between two different districts.

• There are no multiple streets between two districts.

Answer

public class Solution {
    public static int solve(int N, int[] A, int[] B, int[] H) {
        List<List<Integer>> graph = new ArrayList<>(N);
        for (int index = 0; index < N; index++) {
            graph.add(index, new ArrayList<>());
        }

        for (int index = 0; index < A.length; index++) {
            int firstCity = A[index], secondCity = B[index];

            graph.get(firstCity).add(secondCity);
            graph.get(secondCity).add(firstCity);
        }

        Set<Integer> visitedCities = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        int count = -1;
        for (int index = 0; index < H.length; index++) {
            visitedCities.add(H[index]);
            queue.add(H[index]);
        }

        while (queue.size() > 0) {
            int currentQueueSize = queue.size();
            for (int index = 1; index <= currentQueueSize; index++) {
                int city = queue.poll();

                List<Integer> connectedCities = graph.get(city);
                for (int nextCity : connectedCities) {
                    if (!visitedCities.contains(nextCity)) {
                        visitedCities.add(nextCity);
                        queue.add(nextCity);
                    }
                }
            }
            count++;
        }

        return visitedCities.size() == N ? count : -1;
    }

    public static void main(String[] args) {
        System.out.println(solve(6, new int[] { 0, 1, 1, 3, 0 }, new int[] { 1, 2, 3, 4, 5 }, new int[] { 2, 4 }));
        System.out.println(solve(6, new int[] { 0, 1, 1, 3, 0, 4 }, new int[] { 1, 2, 3, 4, 5, 5 }, new int[] { 2, 4 }));
        System.out.println(solve(6, new int[] { 0, 1, 1, 3 }, new int[] { 1, 2, 3, 4 }, new int[] { 2, 4 }));
        System.out.println(solve(3, new int[] { 1 }, new int[] { 2 }, new int[] { 0, 1, 2 }));
    }
}