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 nn rooms numbered from 1n1 - n, and some rooms are connected by corridors. You are given a 2D integer array, corridors, where corridors[i]=[room1,room2]corridors[i] = [room1, room2] indicates that there is a corridor connecting room1room1 and room2room2, allowing a person in the maze to go from room1room1 to room2room2 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, 12311 → 2 → 3 → 1 is a cycle of length 33, but 12341 → 2 → 3 → 4 and 123211 → 2 → 3 → 2 → 1 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:

  • 22 \leq n 100\leq 100
  • 11 \leq corridors.length 5×102\leq 5 \times 10^2
  • corridors[i].length =2= 2
  • 1room1i,room2in1 \leq room1_i, room2_i \leq n
  • room1iroom2iroom1_i \neq room2_i
  • 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 33 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 33. If the next neighbor is the source room, we have found a cycle of length 33. 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 O(V+E)O(V + E), where VV represents the number of vertices and EE 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 O(V×(V+E))O(V \times (V + E)). However, the space complexity of this approach is O(V)O(V).

Optimized approach using graph algo

We solve this problem using the adjacency matrix. We initialize a dictionary, 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 matrix as neighbors[room1] = room2 and neighbors[room2] = room1.

While updating neighbors with the corridor [room1,room2][room1,room2], we know that room1room1 and room2room2 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 room3room3, we conclude that room3room3 is connected to both room1room1 and room2room2. Therefore, we come to know that room1room1, room2room2, and room3room3 are connected with each other, forming a cycle of length 33.

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.