LeetCode 1059: All Paths from Source Lead to Destination Solution
Master LeetCode problem 1059 (All Paths from Source Lead to Destination), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1059. All Paths from Source Lead to Destination
Problem Explanation
Explanation:
This problem can be solved using a Depth First Search (DFS) approach. We can start DFS traversal from the source node and explore all possible paths. If we encounter the destination node, we continue the DFS traversal. While traversing, we need to ensure that all paths lead to the destination node.
We can keep track of visited nodes and also ensure that each node has only one outgoing edge (to the destination node). If we encounter a node with multiple outgoing edges or a dead end, we return false as all paths do not lead to the destination node. :
Solution Code
class Solution {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
}
return dfs(graph, new boolean[n], source, destination);
}
private boolean dfs(Map<Integer, List<Integer>> graph, boolean[] visited, int current, int destination) {
if (visited[current]) {
return false; // Cycle detected
}
if (graph.containsKey(current)) {
visited[current] = true;
for (int next : graph.get(current)) {
if (!dfs(graph, visited, next, destination)) {
return false;
}
}
visited[current] = false;
} else if (current != destination) {
return false; // Dead end encountered
}
return true;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1059 (All Paths from Source Lead to Destination)?
This page provides optimized solutions for LeetCode problem 1059 (All Paths from Source Lead to Destination) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1059 (All Paths from Source Lead to Destination)?
The time complexity for LeetCode 1059 (All Paths from Source Lead to Destination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1059 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1059 in Java, C++, or Python.