LeetCode 2077 - Paths in Maze That Lead to Same Room

The problem asks us to analyze a maze represented as an undirected graph of n rooms connected by corridors. Each corridor allows travel in both directions, and the input corridors lists all such connections.

leetcodemediumgraph-theory

LeetCode Problem 2077

Difficulty: 🟡 Medium
Topics: Graph Theory

Solution

Problem Understanding

The problem asks us to analyze a maze represented as an undirected graph of n rooms connected by corridors. Each corridor allows travel in both directions, and the input corridors lists all such connections. The goal is to determine the number of distinct cycles of length 3, also known as triangles in graph theory, that exist in this maze. Two cycles are considered identical if they include the same set of rooms, regardless of the order of traversal.

The input consists of an integer n representing the number of rooms, and a list of corridors represented as pairs of connected rooms. The constraints indicate that n can go up to 1000, while the number of corridors can be up to 50,000. This means that brute-force enumeration of all paths would be inefficient. Each corridor is unique, and no room is connected to itself.

Edge cases include a maze with no cycles, a fully connected graph where every triplet of rooms forms a triangle, or graphs with disconnected components. These cases test that the algorithm correctly counts only distinct triangles and handles sparse and dense graphs alike.

Approaches

The brute-force approach would involve generating all possible sequences of three rooms and checking if they form a cycle. This approach would check every combination of three rooms and verify connectivity between each pair. While correct, this method has a time complexity of O(n³), which is prohibitive for n up to 1000, resulting in up to 1 billion checks.

The optimal approach leverages graph representation and adjacency checks. By storing the graph as an adjacency list or adjacency set, we can iterate over each edge (u, v) and for each node w adjacent to both u and v, identify a triangle (u, v, w). Using sets allows O(1) membership checks, significantly reducing the number of operations compared to brute force. This method ensures that each triangle is counted only once by enforcing an order (for instance, u < v < w).

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n²) Check all triplets of rooms for cycles
Optimal O(n * d²) O(n²) Use adjacency sets to detect triangles efficiently; d is average node degree

Algorithm Walkthrough

  1. Initialize an adjacency set adj for each room, mapping each room to the set of rooms it is directly connected to. This allows O(1) checks for direct connections.
  2. Initialize a counter triangle_count to zero. This will accumulate the number of distinct triangles.
  3. Iterate through all rooms u from 1 to n. For each room u, consider all pairs of its neighbors (v, w) such that v > u and w > v to avoid counting the same triangle multiple times.
  4. For each such pair (v, w), check if w is in adj[v]. If it is, then u, v, w form a triangle, so increment triangle_count.
  5. Return triangle_count as the confusion score of the maze.

Why it works: By iterating through neighbors in increasing order, we guarantee each triangle is counted exactly once. The adjacency set allows fast verification of connectivity between two nodes. This approach efficiently finds all cycles of length 3 without redundancy.

Python Solution

from typing import List

class Solution:
    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
        adj = {i: set() for i in range(1, n + 1)}
        for u, v in corridors:
            adj[u].add(v)
            adj[v].add(u)
        
        triangle_count = 0
        
        for u in range(1, n + 1):
            neighbors = list(adj[u])
            neighbors.sort()
            for i in range(len(neighbors)):
                v = neighbors[i]
                if v <= u:
                    continue
                for j in range(i + 1, len(neighbors)):
                    w = neighbors[j]
                    if w in adj[v]:
                        triangle_count += 1
        
        return triangle_count

The code first builds an adjacency set for each room, allowing O(1) checks for connections. For each room, it iterates through all pairs of neighbors in sorted order to ensure each triangle is counted exactly once. If the third edge exists between the neighbor pair, a triangle is found and counted.

Go Solution

func numberOfPaths(n int, corridors [][]int) int {
    adj := make([]map[int]bool, n+1)
    for i := 1; i <= n; i++ {
        adj[i] = make(map[int]bool)
    }
    for _, c := range corridors {
        u, v := c[0], c[1]
        adj[u][v] = true
        adj[v][u] = true
    }

    triangleCount := 0

    for u := 1; u <= n; u++ {
        neighbors := make([]int, 0, len(adj[u]))
        for v := range adj[u] {
            neighbors = append(neighbors, v)
        }
        // sort neighbors to enforce u < v < w
        sort.Ints(neighbors)
        for i := 0; i < len(neighbors); i++ {
            v := neighbors[i]
            if v <= u {
                continue
            }
            for j := i + 1; j < len(neighbors); j++ {
                w := neighbors[j]
                if adj[v][w] {
                    triangleCount++
                }
            }
        }
    }

    return triangleCount
}

The Go implementation mirrors the Python approach. It uses a slice of maps to represent the adjacency set and enforces the ordering u < v < w to prevent double-counting. Sorting the neighbor slice ensures proper ordering.

Worked Examples

Example 1: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]

Adjacency sets:

Room Neighbors
1 2, 3, 4
2 1, 4, 5
3 1, 4
4 1, 2, 3
5 2

Triangles found:

  • 1-2-4 (1<2<4)
  • 1-3-4 (1<3<4)

Total = 2.

Example 2: n = 4, corridors = [[1,2],[3,4]]

Adjacency sets:

Room Neighbors
1 2
2 1
3 4
4 3

No triangles found. Total = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n * d²) For each node, we iterate over pairs of its neighbors. d is the average degree.
Space O(n²) Storing the adjacency sets may require up to O(n²) in the worst case for dense graphs.

This approach is efficient for sparse to moderately dense graphs and avoids the prohibitive O(n³) brute-force approach.

Test Cases

# Provided examples
assert Solution().numberOfPaths(5, [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]) == 2  # multiple triangles
assert Solution().numberOfPaths(4, [[1,2],[3,4]]) == 0  # no triangles

# Edge cases
assert Solution().numberOfPaths(3, [[1,2],[2,3],[3,1]]) == 1  # single triangle
assert Solution().numberOfPaths(3, [[1,2],[2,3]]) == 0  # path, no triangle
assert Solution().numberOfPaths(6, [[1,2],[2,3],[3,1],[4,5],[5,6],[6,4]]) == 2  # two disconnected triangles
assert Solution().numberOfPaths(5, [[1,2],[2,3],[3,4],[4,5],[5,1]]) == 0  # cycle length 5, no length 3
Test Why
Example 1 Validates detection of multiple triangles in a complex graph
Example 2 Ensures algorithm handles disconnected components without triangles
Single triangle Validates minimal triangle detection
Path of length 3 Ensures no false positives for non-triangle paths
Two disconnected triangles Validates counting across components
Cycle length 5 Ensures triangles are not detected in larger cycles

Edge Cases

Sparse Graphs: Graphs with few edges may have zero triangles. The algorithm correctly returns 0 because the adjacency checks fail for all neighbor pairs.

Fully Connected Graphs: For a complete graph of n rooms, every triplet forms a triangle. The adjacency sets ensure all triangles are counted exactly once using the ordering u < v < w.

Disconnected Components: Graphs may have isolated clusters. The algorithm correctly iterates over all rooms independently, counting triangles within each component without interference from others. This prevents undercounting or double-counting.

Single Triangle: A graph with exactly three rooms connected in a triangle tests the minimal non-trivial case.