> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/interview/max-distance.md).

# 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:**

```plaintext
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:**

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

***

**Example 3:**

```plaintext
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:**

```plaintext
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

{% code fullWidth="true" %}

```java
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 }));
    }
}
```

{% endcode %}