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

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.