Leetcode #2077: Paths in Maze That Lead to Same Room
In this guide, we solve Leetcode #2077 Paths in Maze That Lead to Same Room in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
A maze consists of n rooms numbered from 1 to n, and some rooms are connected by corridors. You are given a 2D integer array corridors where corridors[i] = [room1i, room2i] indicates that there is a corridor connecting room1i and room2i, allowing a person in the maze to go from room1i to room2i and vice versa.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Graph
Intuition
The data forms a graph, so we should explore nodes and edges systematically.
A traversal ensures we visit each node once while maintaining the needed state.
Approach
Build an adjacency list and traverse with BFS or DFS.
Aggregate results as you visit nodes.
Steps:
- Build the graph.
- Traverse with BFS/DFS.
- Accumulate the required output.
Example
Input: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
Output: 2
Explanation:
One cycle of length 3 is 4 → 1 → 3 → 4, denoted in red.
Note that this is the same cycle as 3 → 4 → 1 → 3 or 1 → 3 → 4 → 1 because the rooms are the same.
Another cycle of length 3 is 1 → 2 → 4 → 1, denoted in blue.
Thus, there are two different cycles of length 3.
Python Solution
class Solution:
def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
g = defaultdict(set)
for a, b in corridors:
g[a].add(b)
g[b].add(a)
ans = 0
for i in range(1, n + 1):
for j, k in combinations(g[i], 2):
if j in g[k]:
ans += 1
return ans // 3
Complexity
The time complexity is O(V+E). The space complexity is O(V).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.