MediumNo. 2077LeetCode Premium
Paths in Maze That Lead to Same Room — LeetCode 2077 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
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.
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 // 3Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2077. Paths in Maze That Lead to Same Room is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2076 | Process Restricted Friend Requests | Hard |
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0332 | Reconstruct Itinerary | Hard |
| 0399 | Evaluate Division | Medium |
Frequently asked questions
- How hard is LeetCode 2077. Paths in Maze That Lead to Same Room?
LeetCode 2077. Paths in Maze That Lead to Same Room is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2077. Paths in Maze That Lead to Same Room?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 2077. Paths in Maze That Lead to Same Room?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 2077. Paths in Maze That Lead to Same Room cover?
LeetCode 2077. Paths in Maze That Lead to Same Room is tagged Graph on LeetCode.
- Is LeetCode 2077. Paths in Maze That Lead to Same Room a premium problem?
Yes. LeetCode 2077. Paths in Maze That Lead to Same Room is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.