1059. All Paths from Source Lead to Destination
All Paths from Source Lead to Destination (LeetCode 1059) 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.
How to solve All Paths from Source Lead to Destination
All Paths from Source Lead to Destination is a Cycle Detection in Directed Graph problem, part of Graph Traversal Patterns (DFS & BFS). Detect cycles in directed graphs using DFS with coloring (white, gray, black) approach.
Work towards the solution in these steps:
- What if we can reach to a cycle from the source node?
- Then the answer will be false, because we eventually get trapped in the cycle forever.
- What if the we can't reach to a cycle from the source node? Then we need to ensure that from all visited nodes from source the unique node with indegree = 0 is the destination node.
The reference solution runs in O(E) time and O(N + E) space.
The All Paths from Source Lead to Destination solution and editorial walks through the full approach with reference code.
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
Examples
Example 1
Input: {"n": 4, "edges": [[0, 1], [0, 2], [1, 3], [2, 3]], "source": 0, "destination": 3}
Output: true
Explanation: Both paths starting at source 0 lead through nodes 1 or 2 and eventually reach destination 3, so every path leads to the destination.
Example 2
Input: {"n": 4, "edges": [[0, 1], [0, 3], [1, 2], [2, 1]], "source": 0, "destination": 3}
Output: false
Explanation: The path from node 0 through nodes 1 and 2 enters a cycle, so not every path from the source leads to destination node 3.
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) time and O(N + E) 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
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
All Paths from Source Lead to Destination FAQ
What is the LeetCode number of All Paths from Source Lead to Destination?
All Paths from Source Lead to Destination is LeetCode problem 1059, rated Medium.
What pattern is used to solve All Paths from Source Lead to Destination?
All Paths from Source Lead to Destination is a Cycle Detection in Directed Graph problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Cycle Detection (Directed Graph) subpattern.
What is the time complexity of All Paths from Source Lead to Destination?
The reference solution runs in O(E) time and O(N + E) space.
Which companies ask All Paths from Source Lead to Destination?
All Paths from Source Lead to Destination has been reported in interviews at Bloomberg.