Problem Description

You are given a maze with n rooms numbered from 1 to n. Some rooms are connected by corridors, and these connections are bidirectional (you can go both ways through a corridor).

The input provides:

• An integer n representing the number of rooms
• A 2D array corridors where each element [room1, room2] represents a corridor connecting room1 and room2

Your task is to find the confusion score of the maze, which is defined as the number of distinct cycles of exactly length 3.

A cycle of length 3 means:

• Starting from a room, visiting exactly 2 other rooms, and returning to the starting room
• For example: 1 → 2 → 3 → 1 is a valid cycle of length 3
• But 1 → 2 → 3 → 4 (doesn't return to start) and 1 → 2 → 3 → 2 → 1 (length 4, not 3) are not valid

Two cycles are considered different if at least one room in the first cycle is not present in the second cycle.

The solution builds an adjacency list representation of the graph where g[i] contains all rooms directly connected to room i. For each room i, it examines all pairs of its neighbors (j, k). If rooms j and k are also connected to each other, then rooms i, j, and k form a triangle (cycle of length 3). Since each triangle is counted 3 times (once for each vertex as the starting point), the final count is divided by 3.

Intuition

To find cycles of length 3, we need to identify triangles in the graph. A triangle exists when three rooms are all connected to each other - room A connects to B, B connects to C, and C connects back to A.

The key insight is that if we're standing at any room in a triangle, we can see the other two rooms as direct neighbors. Moreover, those two neighbors must also be connected to each other to complete the triangle.

This leads us to a straightforward approach: for each room, look at all pairs of its neighbors. If two neighbors are also connected to each other, we've found a triangle.

For example, if room 1 is connected to rooms 2 and 3, and rooms 2 and 3 are also connected to each other, then rooms 1, 2, and 3 form a triangle.

However, there's a counting issue to consider. Each triangle will be discovered three times - once when we examine it from each of its three vertices. When we're at room 1, we'll find the triangle (1, 2, 3). When we're at room 2, we'll find the same triangle as (2, 1, 3). And when we're at room 3, we'll find it as (3, 1, 2). These all represent the same cycle.

Therefore, after counting all triangles from every vertex's perspective, we need to divide the total count by 3 to get the actual number of unique triangles.

The solution uses combinations(g[i], 2) to efficiently generate all pairs of neighbors for each room i, then checks if those two neighbors are connected using if j in g[k]. This approach ensures we systematically find all triangles while avoiding redundant checks.

Learn more about Graph patterns.

Solution Approach

The solution uses a graph-based approach with an adjacency list representation to efficiently find all triangles in the maze.

Step 1: Build the Graph

g = defaultdict(set)
for a, b in corridors:
    g[a].add(b)
    g[b].add(a)

We create an adjacency list using a defaultdict(set) where each room maps to a set of its neighboring rooms. For each corridor [a, b], we add b to the neighbor set of a and vice versa, since corridors are bidirectional. Using sets ensures O(1) lookup time when checking if two rooms are connected.

Step 2: Find All Triangles

ans = 0
for i in range(1, n + 1):
    for j, k in combinations(g[i], 2):
        if j in g[k]:
            ans += 1

We iterate through each room i from 1 to n. For each room, we examine all possible pairs of its neighbors using combinations(g[i], 2). This generates all 2-element combinations from room i's neighbor set.

For each pair (j, k) of neighbors:

• We check if j is in g[k] (equivalently, if k is in g[j] since the graph is undirected)
• If true, rooms i, j, and k form a triangle

Step 3: Adjust for Overcounting

return ans // 3

Since each triangle is counted exactly 3 times (once from the perspective of each of its three vertices), we divide the total count by 3 to get the actual number of unique triangles.

Time Complexity: O(n × d²) where d is the maximum degree of any vertex, as we check all pairs of neighbors for each vertex.

Space Complexity: O(E) where E is the number of corridors, for storing the adjacency list.

Example Walkthrough

Let's walk through a small example with n = 4 rooms and corridors = [[1,2], [2,3], [3,1], [1,4], [2,4]].

Step 1: Build the adjacency list

After processing all corridors:
g[1] = {2, 3, 4}
g[2] = {1, 3, 4}
g[3] = {1, 2}
g[4] = {1, 2}

Step 2: Find triangles from each room's perspective

From room 1 (neighbors: 2, 3, 4):

• Check pair (2, 3): Is 2 in g[3]? Yes! → Triangle found: 1-2-3
• Check pair (2, 4): Is 2 in g[4]? Yes! → Triangle found: 1-2-4
• Check pair (3, 4): Is 3 in g[4]? No → No triangle
• Count from room 1: 2

From room 2 (neighbors: 1, 3, 4):

• Check pair (1, 3): Is 1 in g[3]? Yes! → Triangle found: 2-1-3 (same as 1-2-3)
• Check pair (1, 4): Is 1 in g[4]? Yes! → Triangle found: 2-1-4 (same as 1-2-4)
• Check pair (3, 4): Is 3 in g[4]? No → No triangle
• Count from room 2: 2

From room 3 (neighbors: 1, 2):

• Check pair (1, 2): Is 1 in g[2]? Yes! → Triangle found: 3-1-2 (same as 1-2-3)
• Count from room 3: 1

From room 4 (neighbors: 1, 2):

• Check pair (1, 2): Is 1 in g[2]? Yes! → Triangle found: 4-1-2 (same as 1-2-4)
• Count from room 4: 1

Step 3: Adjust for overcounting

• Total count: 2 + 2 + 1 + 1 = 6
• Each triangle was counted 3 times (once from each vertex)
• Actual number of triangles: 6 ÷ 3 = 2

The two unique triangles are:

1. Rooms 1-2-3
2. Rooms 1-2-4

Therefore, the confusion score is 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × d²) where n is the number of rooms and d is the maximum degree (number of connections) of any room.

• Building the adjacency list from corridors takes O(E) time where E is the number of corridors.
• The main loop iterates through all n rooms.
• For each room i, we generate all pairs of its neighbors using combinations(g[i], 2), which produces C(deg(i), 2) = deg(i) × (deg(i) - 1) / 2 pairs where deg(i) is the degree of room i.
• For each pair (j, k), we check if j in g[k] which takes O(1) average time for a set lookup.
• In the worst case where one room is connected to many others (degree d), we have O(d²) operations for that room.
• Overall: O(E + n × d²), which simplifies to O(n × d²) when d² ≥ E/n.

Space Complexity: O(E) where E is the number of corridors.

• The adjacency list g stores each edge twice (once for each direction), requiring O(E) space.
• The combinations generator and other variables use O(1) additional space.
• Total space complexity is O(E).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Empty or Disconnected Graphs

One common pitfall is not properly handling edge cases where rooms have no connections or the graph has isolated vertices. If a room has fewer than 2 neighbors, combinations(graph[room_i], 2) will return an empty iterator, which is handled correctly. However, developers might try to optimize by skipping rooms with insufficient neighbors but introduce bugs in the process.

Incorrect approach:

for room_i in range(1, n + 1):
    if len(graph[room_i]) < 2:  # Might seem like an optimization
        continue
    for room_j, room_k in combinations(graph[room_i], 2):
        # ... rest of the logic

Why it's fine without the check: The combinations function naturally handles sets with fewer than 2 elements by returning an empty iterator, so the explicit check is unnecessary and could introduce maintenance issues.

2. Using Lists Instead of Sets for Adjacency Storage

Using lists instead of sets for storing neighbors can lead to significant performance degradation and potential duplicate counting issues.

Problematic approach:

graph = defaultdict(list)
for room_a, room_b in corridors:
    graph[room_a].append(room_b)
    graph[room_b].append(room_a)

Issues:

• Checking if room_j in graph[room_k] becomes O(d) instead of O(1) where d is the degree
• If there are duplicate corridors in the input, they would be added multiple times
• Overall time complexity degrades from O(n × d²) to O(n × d³)

Solution: Always use defaultdict(set) to ensure O(1) membership checking and automatic handling of duplicate edges.

3. Forgetting to Divide by 3 or Dividing Incorrectly

Each triangle is discovered exactly 3 times (once from each vertex's perspective). A common mistake is either:

• Forgetting to divide by 3 entirely
• Using regular division / instead of integer division //
• Trying to avoid counting triangles multiple times through complex logic instead of the simple divide-by-3 approach

Incorrect approaches:

# Wrong: Using float division
return triangle_count / 3  # Returns float instead of int

# Wrong: Trying to count each triangle only once with complex logic
visited_triangles = set()
for room_i in range(1, n + 1):
    for room_j, room_k in combinations(graph[room_i], 2):
        if room_j in graph[room_k]:
            triangle = tuple(sorted([room_i, room_j, room_k]))
            visited_triangles.add(triangle)
return len(visited_triangles)

Solution: Simply count all triangles and use integer division by 3: return triangle_count // 3

4. Off-by-One Errors with Room Numbering

Since rooms are numbered from 1 to n (not 0 to n-1), iterating incorrectly can miss rooms or cause index errors.

Incorrect approach:

# Wrong: Starting from 0
for room_i in range(n):  # Should be range(1, n + 1)
    # ...

# Wrong: Going up to n-1
for room_i in range(1, n):  # Should be range(1, n + 1)
    # ...

Solution: Always use range(1, n + 1) when iterating through rooms to match the 1-indexed room numbering system.