Solving HackerRank Problem Rust & Murderer in Java

Problem

Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn't show the village roads (or side lanes) on it and shows only the main roads.

See full description of Rust & Murderer

Solution

Since we know the graph of main roads, but need  to travel only on side roads, we will need to  get the inverse of the main road graph. Then we can just run a bfs shortest path on the new graph          

Optimisation: Instead of inversing the graph, we can just run BFS on all non-neighbors thus removing the inverse graph step Per test case

Time Complexity: O(N + M) //We must visit every node once and we do so my way of the main roads

Space Complexity: O(N)

Credit: @github.com/RyanFehr