Solution: Paths in Maze That Lead to Same Room
Let’s solve the Paths in Maze That Lead to Same Room problem using the Graphs pattern.
Statement
A maze consists of rooms numbered from , and some rooms are connected by corridors. You are given a 2D integer array, corridors
, where indicates that there is a corridor connecting and , allowing a person in the maze to go from to and vice versa.
The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.
For example, is a cycle of length , but and are not.
Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.
Return the confusion score of the maze.
Constraints:
-
n
-
corridors.length
corridors[i].length
- There are no duplicate corridors.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
A naive approach for finding cycles of length in a given set of rooms is based on DFS traversal. We apply DFS on a room and traverse until we visit its neighbors up to a depth of . If the next neighbor is the source room, we have found a cycle of length . Otherwise, we have not. Repeat this process for all the other rooms, and count all the cycles of length 3.
The time complexity for DFS traversal on a single node is , where represents the number of vertices and represents the number of edges in the graph. Since we perform DFS traversal on every node in the graph, the overall time complexity can be expressed as . However, the space complexity of this approach is .
Optimized approach using graph algo
We solve this problem using the adjacency list. We initialize a map, neighbors
, containing all rooms as keys and their neighboring rooms as corresponding values. Since corridors[i]=[room1,room2]
represents a corridor showing that the two rooms are connected, we update the adjacency list as neighbors[room1] = room2
and neighbors[room2] = room1
.
While updating neighbors
with the corridor , we know that and are directly connected. After updating neighbors
with this corridor, we can look for any common room that exists in both neighbors[room1]
and neighbors[room2]
. This can be done by taking the intersection of neighbors[room1]
and neighbors[room2]
. If we find any common room, say , we conclude that is connected to both and . Therefore, we come to know that , , and are connected with each other, forming a cycle of length .
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.