educative.io

Optimized solution for Paths in Maze

The provided solution has time complexity O(nm) and space complexity O(n^2). Can we get this down to O(n+m) for each with a DFS approach?

def number_of_paths(n, corridors):

    def dfs(parent, node):
        nonlocal result, visited
        for neighbor in graph[node]:
            if neighbor in visited:
                if parent and parent in graph[neighbor]:
                    result += 1
            else:
                visited.add(neighbor)
                dfs(node, neighbor)

    graph = [set() for _ in range(n + 1)]
    for corridor in corridors:
        graph[corridor[0]].add(corridor[1])
        graph[corridor[1]].add(corridor[0])
    result = 0
    visited = set()
    for node in range(1, n + 1):
        if node not in visited:
            visited.add(node)
            dfs(None, node)
    return result

Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Solution: Paths in Maze That Lead to Same Room - Grokking Coding Interview Patterns in Python