2077. Paths in Maze That Lead to Same Room


Problem Description

The problem involves finding the confusion score of a maze, which is determined by counting the number of unique cycles of length 3 among the rooms. A cycle of length 3 would look like a trip from one room to a second, then to a third, and back to the first, without repetition of rooms or revisiting the starting room before the cycle is complete. The array corridors provides the connections between rooms, where each connection enables two-way travel between the connected rooms.

For example, if we have a cycle 1 β†’ 2 β†’ 3 β†’ 1, it counts as one valid cycle. We need to ensure that each trio of rooms forms exactly one cycle for counting purposes. Cycles with more than three rooms or cycles that don't return to the starting room after exactly three steps are not considered in the confusion score.

The goal is to calculate the total number of these length 3 cycles in the entire maze based on the corridors provided.

Intuition

To find all possible cycles of length 3, we first convert the corridors list into a graph representation where each room has a list of directly connected rooms. A defaultdict(set) is used to facilitate this as it automatically handles the creation of keys and prevents duplicate entries for connections between rooms.

Once we have the graph, for each room i, we look at all pairs of its connected rooms (using the combinations function from the itertools module). For every pair of connected rooms j and k, we check if there's a direct connection from j to k. If such a connection exists, we've found a cycle of length 3 (i β†’ j β†’ k β†’ i), so we increment a counter ans. However, each cycle will be counted three times (once for each room in the cycle as the starting room), so we'll divide the total count by 3 to get the correct number of unique cycles.

By iterating through all rooms and their connections, we comprehensively check every possibility for cycles of length 3 and calculate the confusion score to return it.

Solution Approach

The Reference Solution Approach employs a graph data structure, a combinations utility, and some simple arithmetic. Here's a step-by-step breakdown of the implementation:

  1. Graph Representation: First, we need to represent the maze as a graph where the nodes are rooms, and edges are the corridors between them. We use a defaultdict(set) from Python's collections module to make this easy. A set is chosen for each room's connections because it prevents duplication of corridors and allows for quick membership testing.

  2. Building the Graph: With the input corridors list, which contains pairs of rooms connected by corridors, we iterate through each pair. For each corridor (a, b), we add room b to the set of connections for room a and vice versa, effectively constructing an undirected graph.

  3. Searching for Cycles: To find all unique 3-room cycles, we look at each room i and consider all combinations of its connected rooms. We use Python's itertools.combinations() to generate all unique pairs of connected rooms (j, k) without repetition.

  4. Cycle Validation: For each pair of rooms (j, k) connected to room i, we check if j and k are directly connected to each other - this would complete the cycle i β†’ j β†’ k β†’ i. If a direct connection exists, we increment a counter ans. This process ensures that we only count cycles once and that they are of length 3.

  5. Avoiding Double Counting: Since each cycle appears three times (once starting at each room), we divide the total count by 3 at the end to get the number of unique cycles. The floor division operator // ensures that the result is an integer.

Here is a snippet of how this is being implemented in code:

1g = defaultdict(set)
2for a, b in corridors:
3    g[a].add(b)
4    g[b].add(a)
5
6ans = 0
7for i in range(1, n + 1):
8    for j, k in combinations(g[i], 2):
9        if j in g[k]:
10            ans += 1
11
12return ans // 3

In summary, the solution involves constructing an undirected graph, identifying all possible unique cycles of length 3 by examining each node's connections, validating those cycles, and then ensuring that we count each cycle only once by dividing the count by three. This approach leads to an efficient calculation of the confusion score for any given maze represented by its corridors.

πŸ’ͺ
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small maze with 4 rooms and a set of corridors that connect them:

Corridors: [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]

Graph Representation

Following the solution approach, we first convert the list of corridors into a graph representation.

1Room 1: connected to Room 2 and Room 3
2Room 2: connected to Room 1, Room 3, and Room 4
3Room 3: connected to Room 1, Room 2, and Room 4
4Room 4: connected to Room 2 and Room 3

Building the Graph

The graph constructed from the corridors looks like this:

1g = defaultdict(set)
2g[1] = {2, 3}
3g[2] = {1, 3, 4}
4g[3] = {1, 2, 4}
5g[4] = {2, 3}

Searching for Cycles

Next, we consider each room and look for all combinations of connected rooms to find cycles of length 3.

For room 1: The combinations of connected rooms are (2, 3).

For room 2: The combinations of connected rooms are (1, 3), (1, 4), and (3, 4).

For room 3: The combinations of connected rooms are (1, 2), (1, 4), and (2, 4).

For room 4: The combinations of connected rooms are (2, 3).

Cycle Validation

We then check whether the combinations actually form cycles of length 3.

  • For room 1, the pair (2, 3) is connected, forming a cycle: 1 β†’ 2 β†’ 3 β†’ 1.
  • For room 2, the pair (3, 4) is connected, forming a cycle: 2 β†’ 3 β†’ 4 β†’ 2.
  • For room 3, the pair (2, 4) is connected, forming a cycle: 3 β†’ 2 β†’ 4 β†’ 3.
  • For room 4, the pair (2, 3) is connected, but this cycle was already counted when considering room 2, so it's not unique.

Avoiding Double Counting

Each of the valid cycles identified will appear three times, once for each room in the cycle. We've found the cycles:

11 β†’ 2 β†’ 3 β†’ 1
22 β†’ 3 β†’ 4 β†’ 2
33 β†’ 2 β†’ 4 β†’ 3

These are counted for rooms 1, 2, and 3 respectively. Since each of these cycles is counted thrice (once from each room’s perspective), we get a total count of 3 cycles. However, there is only one unique cycle for each set.

Final Answer

By dividing the total count by 3, we obtain the final answer:

1ans = 3 // 3 = 1

So, the confusion score for the maze with these corridors is 1. There is only one unique cycle of length 3 among the rooms in this maze.

Python Solution

1from collections import defaultdict
2from itertools import combinations
3
4class Solution:
5    def numberOfPaths(self, numNodes: int, corridors: List[List[int]]) -> int:
6        # Create a graph as a dictionary with default value type 'set', for adjacency list representation
7        graph = defaultdict(set)
8
9        # Build the graph, where each node has a set of its adjacent nodes
10        for first, second in corridors:
11            graph[first].add(second)
12            graph[second].add(first)
13
14        # Initialize counter to keep track of the number of triangular paths
15        trianglePathsCount = 0
16
17        # Iterate through each node
18        for node in range(1, numNodes + 1):
19            # Iterate through all possible pairs of adjacents nodes
20            for neighbor1, neighbor2 in combinations(graph[node], 2):
21                # Check if this pair of nodes forms a triangle with the current node
22                if neighbor1 in graph[neighbor2]:
23                    # If so, increment the counter
24                    trianglePathsCount += 1
25      
26        # Since each triangle is counted three times, divide the result by 3
27        return trianglePathsCount // 3
28

Java Solution

1class Solution {
2    public int numberOfPaths(int n, int[][] corridors) {
3        // Graph represented as an array of hashsets where each hashset is a list of connected nodes
4        Set<Integer>[] graph = new Set[n + 1];
5      
6        // Initialize each node's adjacency list
7        for (int i = 0; i <= n; ++i) {
8            graph[i] = new HashSet<>();
9        }
10      
11        // Build the graph from corridor connections
12        for (int[] corridor : corridors) {
13            int nodeA = corridor[0];
14            int nodeB = corridor[1];
15            graph[nodeA].add(nodeB);
16            graph[nodeB].add(nodeA);
17        }
18      
19        // Count the number of valid paths
20        int pathCount = 0;
21      
22        // Iterate over every node to find potential triangles
23        for (int currentNode = 1; currentNode <= n; ++currentNode) {
24            // Get neighbors of the current node
25            var neighbors = new ArrayList<>(graph[currentNode]);
26            int neighborCount = neighbors.size();
27          
28            // Check every pair of neighbors to find a triangle
29            for (int i = 0; i < neighborCount; ++i) {
30                for (int j = i + 1; j < neighborCount; ++j) {
31                    int neighborA = neighbors.get(i);
32                    int neighborB = neighbors.get(j);
33                  
34                    // If the neighbors are also connected, we found a triangle, increment the count
35                    if (graph[neighborB].contains(neighborA)) {
36                        pathCount++;
37                    }
38                }
39            }
40        }
41      
42        // Since each triangle is counted 3 times (once for each vertex), divide by 3 to get the correct count
43        return pathCount / 3;
44    }
45}
46

C++ Solution

1class Solution {
2public:
3    int numberOfPaths(int n, vector<vector<int>>& corridors) {
4        // Initialize an adjacency list for the graph where each node
5        // has a set of connected nodes (to represent an undirected graph)
6        vector<unordered_set<int>> graph(n + 1);
7      
8        // Populate the graph with corridors data
9        for (const auto& corridor : corridors) {
10            // Extracting endpoints of the corridor
11            int node1 = corridor[0], node2 = corridor[1];
12            // Since this is an undirected graph, add each node to the other's adjacency list
13            graph[node1].insert(node2);
14            graph[node2].insert(node1);
15        }
16      
17        // Initialize a variable to store the number of triangular paths found
18        int answer = 0;
19      
20        // Iterate over each node in the graph to check for triangular paths
21        for (int current = 1; current <= n; ++current) {
22            // Create a vector to easily iterate over the adjacent nodes
23            vector<int> neighbors;
24            neighbors.assign(graph[current].begin(), graph[current].end());
25          
26            // Iterate over pairs of neighbors to check if they are also connected to each other
27            for (int i = 0; i < neighbors.size(); ++i) {
28                for (int j = i + 1; j < neighbors.size(); ++j) {
29                    int neighbor1 = neighbors[i], neighbor2 = neighbors[j];
30                  
31                    // If neighbor1 is connected to neighbor2, it forms a triangular path
32                    answer += graph[neighbor2].count(neighbor1);
33                }
34            }
35        }
36      
37        // Since each triangular path is counted three times (once for each vertex),
38        // we divide by 3 to get the correct number of unique paths.
39        return answer / 3;
40    }
41};
42

Typescript Solution

1// Interface representing a pair of integers
2interface Pair {
3    first: number;
4    second: number;
5}
6
7// Function to calculate the number of triangular paths
8function numberOfPaths(n: number, corridors: Pair[]): number {
9    // Initialize an adjacency list for the graph
10    const graph: Set<number>[] = new Array(n + 1);
11  
12    // Fill the graph array with empty sets for each node
13    for (let i = 0; i <= n; i++) {
14        graph[i] = new Set();
15    }
16  
17    // Populate the graph with corridors data
18    for (const corridor of corridors) {
19        // Extracting endpoints of the corridors
20        const node1 = corridor.first;
21        const node2 = corridor.second;
22
23        // Add each node to the other's adjacency list
24        graph[node1].add(node2);
25        graph[node2].add(node1);
26    }
27  
28    // Variable to store the number of triangular paths found
29    let answer = 0;
30  
31    // Check each node for triangular paths
32    for (let currentNode = 1; currentNode <= n; currentNode++) {
33        // Create an array of neighbors from the current node's adjacency list
34        const neighbors: number[] = Array.from(graph[currentNode]);
35
36        // Iterate over pairs of neighbors to check for direct connections
37        for (let i = 0; i < neighbors.length; i++) {
38            for (let j = i + 1; j < neighbors.length; j++) {
39                const neighbor1 = neighbors[i];
40                const neighbor2 = neighbors[j];
41
42                // If neighbor1 is directly connected to neighbor2, a triangular path is formed
43                if (graph[neighbor2].has(neighbor1)) {
44                    answer++;
45                }
46            }
47        }
48    }
49  
50    // Every triangle path has been counted 3 times, divide by 3 to normalize
51    return answer / 3;
52}
53
54// Example usage
55// Define some corridors as per the interface Pair
56const corridors: Pair[] = [
57    { first: 1, second: 2 },
58    { first: 1, second: 3 },
59    { first: 2, second: 3 }
60];
61
62// Call our function with n nodes and the corridors array
63const trianglePaths = numberOfPaths(3, corridors);
64console.log(trianglePaths); // Output should be 1 as there is one triangle path (1 - 2 - 3)
65

Time and Space Complexity

Time Complexity:

The given code consists of building a graph and then finding all the triangles in it. Here's a breakdown of the time complexity:

  1. Building the adjacency graph g has a time complexity of O(E), where E is the number of edges or corridors because we iterate over each corridor to build the graph.
  2. The outer loop runs n times (where n is the number of rooms), so it has a time complexity of O(N).
  3. Inside the outer loop, the combinations function is called. Each call of combinations can generate up to O(d^2) combinations, where d is the degree (number of edges) of node i. The degree can vary for each node, and in the worst case, it could be n-1, which would result in O((n-1)^2) combinations for that node.
  4. Checking if j is in g[k] is O(1) with the hash set data structure, and this is done once for each combination generated in the previous step. So this operation can be potentially O(n^2) in the worst case for each node.
  5. Finally, the ans is divided by 3 outside of the loops, which is a constant-time operation O(1).

Taking all these into account, the total time complexity is O(N + E + N * (n-1)^2), which simplifies to O(N * (n-1)^2) in the worst-case scenario when the graph is dense (since N dominates E). In other words, the time complexity can be expressed as O(N^3) when each node is connected to every other node.

Space Complexity:

The space complexity of the code is mainly due to the storage required for the adjacency graph.

  1. The adjacency graph g will have a space complexity of O(V + E), where V is the number of nodes and E is the number of edges, to store all vertices and their edges.
  2. There is some additional overhead due to the storage of combinations in the inner loop, but this does not increase space complexity as it is temporary and does not depend on the size of the input.
  3. The space complexity of other variables used (like ans, i, j, k) is O(1).

The dominant term in the space complexity is the storage for the graph, which gives us O(V + E) space complexity.

Putting the time and space complexities together, we have:

  • Time Complexity: O(N^3)
  • Space Complexity: O(V + E)
😈
Become an
Algo Monster

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«