LeetCode Solutions Blog

Paths in Maze That Lead to Same Room

Number: 2218

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an undirected graph representing a maze with n rooms and corridors between them, determine the confusion score defined as the number of unique cycles of exactly length 3 (triangles) in the graph.

Key Insights

The problem reduces to counting the number of triangles in an undirected graph.
Each triangle (cycle of length 3) will be counted three times if iterating over all edges, so the final count must be divided by 3.
Use an adjacency list (with sets) to efficiently check whether two nodes have a common neighbor.
Iterating over each corridor and computing the intersection of neighbors enables fast counting of triangles.

Space and Time Complexity

Time Complexity: O(E * min(deg(u), deg(v))) where E is the number of corridors; in worst-case scenarios this is efficient given the constraints. Space Complexity: O(n + E) for storing the adjacency list.

Solution

We use an adjacency list (using sets for quick membership tests) to represent the graph. For each corridor (edge) connecting two rooms, we find the intersection of the neighbor sets of the two rooms (this gives common neighbors that can close a triangle). The sum of all intersections gives three times the number of triangles (since each triangle gets counted at each of its three edges), so we divide the total count by 3 to get the final answer.

Code Solutions

# Build the adjacency list as a dictionary where keys are nodes and values are sets of neighboring nodes.
# For each corridor (edge), compute the intersection of neighbors between the two nodes.
# Sum these counts and then divide by 3 to avoid multiple counting of each triangle.

def count_triangles(n, corridors):
    # Initialize the graph with empty sets for each room (node)
    graph = {i: set() for i in range(1, n+1)}
    
    # Add corridors to the graph (undirected)
    for room1, room2 in corridors:
        graph[room1].add(room2)
        graph[room2].add(room1)
    
    triangle_count = 0
    # For each corridor, count common neighbors
    for room1, room2 in corridors:
        # Use the smaller set for intersection to minimize time
        if len(graph[room1]) > len(graph[room2]):
            room1, room2 = room2, room1
        # Count the number of rooms that are neighbors to both room1 and room2.
        common_neighbors = graph[room1].intersection(graph[room2])
        triangle_count += len(common_neighbors)
    
    # Each triangle is counted 3 times (once for each edge in the triangle)
    return triangle_count // 3

# Example usage:
n = 5
corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
print(count_triangles(n, corridors))  # Expected output: 2