Delivery Zone Hop Count
At Zomato, optimizing delivery routes is crucial for efficiency and customer satisfaction. Imagine a city mapped out into various "delivery zones," each representing a distinct area like a restaurant hub or a residential locality. Drivers navigate between these zones using direct road segments. To ensure quick deliveries, we need to determine the minimum number of road segments (hops) a driver must traverse to get from a starting delivery zone to a target delivery zone.
Your task is to implement a function that calculates the minimum number of direct road segments (hops) required to travel from a given startZone to a targetZone within a city's delivery network.
The function minDeliveryHops takes three arguments:
graph: A 2D array (adjacency list) representing the delivery network. graph[i] is an array of integers, where each integer j indicates that there's a direct road segment from zone i to zone j. The graph is unweighted and undirected (if i connects to j, j connects to i).startZone: An integer representing the ID of the starting delivery zone.targetZone: An integer representing the ID of the target delivery zone.The function should return:
targetZone from startZone.-1 if the targetZone is unreachable from the startZone.startZone == targetZone.startZone is the same as targetZone, the number of hops is 0.graph[i] contains j, assume graph[j] contains i. However, the input graph will be provided such that both directions are explicitly listed (e.g., if i connects to j, then j connects to i in the input adjacency list).Examples
Example 1
Input:
graph = [[1], [0, 2], [1, 3], [2]], startZone = 0, targetZone = 3
Output:
3
Note:
Path: 0 -> 1 -> 2 -> 3. This takes 3 hops.
Example 2
Input:
graph = [[1, 2], [0, 3], [0, 4], [1], [2]], startZone = 0, targetZone = 3
Output:
2
Note:
Path 1: 0 -> 1 -> 3 (2 hops). Path 2: 0 -> 2 -> 4 (2 hops, but not to target 3). The shortest path is 0 -> 1 -> 3, which is 2 hops.
Example 3
Input:
graph = [[1], [0], [3], [2]], startZone = 0, targetZone = 3
Output:
-1
Note:
Zone 0 is connected to zone 1. Zone 2 is connected to zone 3. There is no path between the component {0,1} and {2,3}. Therefore, target zone 3 is unreachable from start zone 0.
Example 4
Input:
graph = [[1], [0, 2], [1]], startZone = 1, targetZone = 1
Output:
0
Note:
The start zone is already the target zone, so 0 hops are needed.
Constraints
1 <= N <= 100 (Number of delivery zones/nodes)0 <= M <= N * (N - 1) / 2 (Number of road segments/edges)0 <= startZone, targetZone < Ngraph[i] will be a valid zone ID (0 to N-1).graph will always be a valid adjacency list representation where graph[i] lists neighbors of i.startZone == targetZone and disconnected components.Loading editor...