Skip to main content
Talentd

Paths in Maze That Lead to Same Room - Solution & Explanation

MediumPremiumFree on FleetCodeGraph5 min readAsked at: Google
Practice this problem

Problem Statement

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

 

Example 1:

Input: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
Output: 2
Explanation:
One cycle of length 3 is 4 → 1 → 3 → 4, denoted in red.
Note that this is the same cycle as 3 → 4 → 1 → 3 or 1 → 3 → 4 → 1 because the rooms are the same.
Another cycle of length 3 is 1 → 2 → 4 → 1, denoted in blue.
Thus, there are two different cycles of length 3.

Example 2:

Input: n = 4, corridors = [[1,2],[3,4]]
Output: 0
Explanation:
There are no cycles of length 3.

 

Constraints:

  • 2 <= n <= 1000
  • 1 <= corridors.length <= 5 * 104
  • corridors[i].length == 2
  • 1 <= room1i, room2i <= n
  • room1i != room2i
  • There are no duplicate corridors.

Approach Overview

Problem Overview: You are given an undirected maze of rooms connected by corridors. The task is to count distinct paths of the form a → b → c → a where you start and end in the same room without repeating edges. In graph terms, this is counting the number of triangles in an undirected graph.

Approach 1: Brute Force Triplet Check (O(n^3) time, O(n^2) space)

Construct an adjacency matrix so you can check connectivity in constant time. Then iterate through every triple of rooms (i, j, k). If edges (i, j), (j, k), and (k, i) exist, they form a valid cycle of length three. This directly counts triangles in the graph. The downside is the cubic iteration over all node triplets, which becomes expensive when the number of rooms grows. This method mainly demonstrates the underlying structure of the problem.

Approach 2: Edge Iteration with Common Neighbors (O(E * min(deg(u),deg(v))) time, O(E) space)

Store the graph using an adjacency list backed by hash sets. For each corridor (u, v), look for rooms that connect to both u and v. Every common neighbor w forms a triangle u → v → w → u. To do this efficiently, iterate through the smaller adjacency set and check membership in the other using constant-time hash lookups. Each triangle is discovered three times (once per edge), so divide the final count by three.

This approach works well because most real graphs are sparse. The work per edge becomes proportional to the smaller node degree rather than the total number of nodes. Using an adjacency list keeps memory usage linear relative to the number of corridors.

Approach 3: Degree Ordering Optimization (O(E * sqrt(E)) typical, O(E) space)

You can further reduce checks by ordering nodes by degree and only exploring edges in a consistent direction (from lower degree to higher degree). This avoids repeatedly scanning large neighbor lists. For each directed edge under this ordering, count intersections between forward neighbors. This trick appears frequently in triangle-counting algorithms for large graphs.

Recommended for interviews: The adjacency-set intersection approach is what interviewers typically expect. The brute force method shows you understand the triangle definition, but the optimized solution demonstrates practical graph handling, efficient neighbor lookup, and awareness of sparse graph behavior.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet CheckO(n^3)O(n^2)Small graphs or when demonstrating the triangle definition
Edge + Common Neighbor IntersectionO(E * min(deg(u),deg(v)))O(E)General case for sparse graphs; typical interview solution
Degree Ordered Triangle Counting~O(E * sqrt(E))O(E)Large graphs where node degrees vary widely

Video Solution

[Leetcode] 2077. Paths in Maze That Lead to Same Room • Simple Code • 624 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Paths in Maze That Lead to Same Room easy or hard?
The problem is rated Medium because it requires recognizing that the task reduces to triangle counting in an undirected graph. Once you model the maze as a graph and use adjacency sets for fast neighbor checks, the implementation becomes straightforward.
Paths in Maze That Lead to Same Room Python/Java solution
Implement the graph using a dictionary or map from node to a hash set of neighbors. Iterate through each edge and count shared neighbors using set lookups. The same logic works across Python, Java, C++, and Go with hash-based adjacency sets.
What is the best approach for Paths in Maze That Lead to Same Room?
The most practical approach counts triangles using adjacency sets. For every edge (u, v), check the intersection of neighbors of u and v. Each common neighbor forms a triangle. The complexity is O(E * min(deg(u), deg(v))) with O(E) space, which performs well for sparse graphs.
Is Paths in Maze That Lead to Same Room asked at Google/Amazon/Meta?
Triangle counting and cycle detection in graphs appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test your ability to use adjacency lists, hash sets, and efficient neighbor intersection strategies.
What data structure is used in Paths in Maze That Lead to Same Room?
The solution relies on an adjacency list representation of the graph. Each node stores neighbors in a hash set so membership checks run in O(1). This makes intersection checks between neighbor lists efficient.
What is the time complexity of Paths in Maze That Lead to Same Room?
The optimal adjacency-set approach runs in O(E * min(deg(u), deg(v))) time where E is the number of corridors and deg(x) is the degree of a room. Space complexity is O(E) for storing the adjacency list. A brute force alternative can take O(n^3) time using an adjacency matrix.
How to solve Paths in Maze That Lead to Same Room in O(E * min(deg)) time?
Build an adjacency list where each room stores its neighbors in a hash set. For each edge (u, v), iterate through the smaller neighbor set and check if the node also appears in the other set. Every shared neighbor forms a triangle u → v → w → u. Divide the total count by three because each triangle is discovered once per edge.

Ready to solve this problem?

Practice Paths in Maze That Lead to Same Room with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distance to a Cycle in Undirected Graph

Next

Find if Path Exists in Graph