Deepen your knowledge of graph theory, algorithms, practical solutions, and real-world applications.

Coding

Represents a set of connected nodes or vertices, allowing for traversal and analysis of relationships or connections between data points.

Graphs

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

#
## 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 100$
- $1  \leq$ `corridors.length` $\leq 5 \times 10^2$
- `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 list. 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 list 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:

Let’s solve the Paths in Maze That Lead to Same Room problem using the Graphs pattern.


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.

Solution: Paths in Maze That Lead to Same Room

Statement▼

Solution: Paths in Maze That Lead to Same Room

Statement▼