All Paths from Source Lead to Destination

All Paths from Source Lead to Destination is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Cycle Detection (Directed Graph) subpattern.

Problem statement

You are given a directed graph with n nodes labeled from 0 to n - 1, represented by a list of directed edges edges, where each edges[i] = [ui, vi] indicates a directed edge from node ui to node vi. You are also given two integers, source and destination.

Return true if and only if every possible path starting from source eventually leads to destination. Specifically, this means:

- At least one path exists from source to destination. - If a path leads to a node with no outgoing edges, that node must be destination. - The graph does not contain cycles that can be reached from source (i.e., no path from source can enter a cycle).

Otherwise, return false.

Constraints: - 1 <= n <= 10^4 - 0 <= edges.length <= 10^4 - 0 <= ui, vi, source, destination < n

Topics and companies

Topics: Graph, Topological Sort.

Reported in interviews at Bloomberg.

How to practise All Paths from Source Lead to Destination on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(E), where E is the number of edges. Each edge and node is visited at most once due to memoization with the status array. time and O(N + E), where N is the number of nodes and E is the number of edges. The adjacency list takes O(E) space, and the status array takes O(N) space. The recursion stack can go up to O(N) in the worst case. space.

Open All Paths from Source Lead to Destination in the code editor, or read the All Paths from Source Lead to Destination editorial for a worked solution with its approach and complexity analysis.

Where All Paths from Source Lead to Destination sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Cycle Detection (Directed Graph) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to All Paths from Source Lead to Destination

Other problems that use the same Graph DFS - Cycle Detection (Directed Graph) and Graph Traversal Patterns (DFS & BFS) techniques:

• Course Schedule — Medium, same subpattern
• Course Schedule II — Medium, same subpattern
• Find Eventual Safe States — Medium, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• Build a Matrix With Conditions — Hard, same pattern