Solution: Paths in Maze That Lead to Same Room

Statement

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

• $2 \leq$ n $\leq 1000$
• $1 \leq$ corridors.length $\leq 5 \times 10^4$
• corridors[i].length $= 2$
• $1 \leq room1_i, room2_i \leq n$
• $room1_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 $3$ 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 $3$. If the next neighbor is the source room, we have found a cycle of length $3$. 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)$, where $V$ represents the number of vertices and $E$ 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 \times (V + E))$. However, the space complexity of this approach is $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]$, we know that $room1$ and $room2$ 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 $room3$, we conclude that $room3$ is connected to both $room1$ and $room2$. Therefore, we come to know that $room1$, $room2$, and $room3$ are connected with each other, forming a cycle of length $3$.

Let’s look at the following illustration to get a better understanding of the solution: