Java Solution For HackerRank Problem: Rust & Murderer
Solving HackerRank Problem Rust & Murderer in Java
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
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)