Find if Path Exists in Graph (LeetCode 1971)
A graph has n nodes, numbered from 0 to n - 1. The list edges describes its connections. Each pair [u, v] is one edge, and it joins node u and node v in both directions, so you can walk it either way.
You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.
Worked Examples
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2truen = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5false⚖️Formal Constraints & Bounds
1 <= n <= 2 * 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ui, vi <= n - 1ui != vi0 <= source, destination <= n - 1There are no duplicate edges.
There are no self-edges.
Core Insight
Mark a node in seen at the moment it is added to queue: a node with two parents is then queued once, and a cycle cannot refill the queue, so the loop always ends.
Real-World Scenario & Production Applications
Checking whether one computer can send data to another computer in a network, or whether one station can reach another station on a railway map, is the same question.
Step-by-Step Execution Trace Table
Step-by-Step Decision Trace (Example 2)
- Step 1 (source is not destination):
source = 0anddestination = 5are different nodes, so a search is needed. - Step 2 (build
graph): every edge is stored in both directions.graph = {0: [1, 2], 1: [0], 2: [0], 3: [5, 4], 5: [3, 4], 4: [5, 3]}. - Step 3 (start):
seen = {0}andqueue = [0]. The source is marked before the loop starts. - Step 4 (pop 0):
node = 0. Neighbour1is not the destination and is not inseen, soseen = {0, 1}andqueue = [1]. Neighbour2is new too, soseen = {0, 1, 2}andqueue = [1, 2]. - Step 5 (pop 1):
node = 1. Its only neighbour is0. Node0is already inseen, so it is not queued again. - Step 6 (pop 2):
node = 2. Its only neighbour is0, which is already inseen. Nothing is queued. - Step 7 (empty queue):
queue = []. Every node that can be reached from node 0 was expanded, and none of them is node 5.
Search complete: return False.
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2Expected:true| 1 | if source == destination: return True |
| 2 | graph = lists of neighbours, built from edges (both directions) |
| 3 | seen = {source} |
| 4 | queue = deque([source]) |
| 5 | while queue: |
| 6 | node = queue.popleft() |
| 7 | for neighbour in graph[node]: |
| 8 | if neighbour == destination: return True |
| 9 | if neighbour not in seen: |
| 10 | seen.add(neighbour) |
| 11 | queue.append(neighbour) |
| 12 | return False |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A graph is a set of nodes joined by edges. In a tree, every node has one parent. In a graph, one node can be reached from two parents, and the edges can form a cycle. A cycle is a path that comes back to the node where it started.
Breadth-first search (BFS) on a graph uses the same queue as level-order traversal. It adds one rule: a set named seen records every node that has been added to queue. A node that is already in seen is never added again.
🚆 Real-World Example: Train Stations
Each station is a node and each track between two stations is an edge. You start at one station and want to know whether you can reach another station. You keep a list of the stations that you have already planned to visit. Before you plan a station, you check the list. Without the list, two tracks that lead to the same station, or a loop of tracks, would put the same station in your plan again and again.
🔑 Why It Works
seen.add(neighbour) runs in the same step as queue.append(neighbour). A node that waits in queue is therefore already marked, so a second parent cannot add it again. Each node enters queue once, so the loop runs at most n times and ends even when the graph has a cycle.
Adding a node without checking
seen: A graph can have a cycle. Without the check, every neighbour goes intoqueueagain and again, so the loop never ends whendestinationcannot be reached. Add a node toseenat the moment it joinsqueue.Adding only one direction of each edge: An edge
[u, v]joins both nodes. Addvto the neighbours ofuanduto the neighbours ofv, or a search that starts atvfinds no neighbour.Skipping the case
source == destination: A path of length 0 exists, even whenedgesis empty. ReturnTruebefore the search starts.Marking a node when it leaves
queueinstead of when it joins: A node that waits inqueueis not yet inseen, so a second parent adds it again and the same node is expanded many times.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement gives n nodes and a list of two-way edges, and asks whether destination can be "reached" from source. The input is a graph that can have cycles, and the search starts from one node. That is Graph BFS with a seen set.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every node in seen is in queue or has already left it, so each node is added to queue exactly once. The decision: a neighbour that is not in seen joins seen and queue together, and a neighbour that is already in seen is skipped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use BFS with a seen set. If source is destination, I return True at once. Otherwise I build a list of neighbours for each node from the edges, adding each edge in both directions, because it can be walked either way. I mark source in seen, put it in the queue, and repeat: take the oldest node, and look at each of its neighbours. If a neighbour is the destination, I return True. If it is not in seen, I add it to seen and to the queue in the same step. So every node waits in the queue at most once, a node with two parents is expanded once, and a cycle cannot keep the loop running. If the queue becomes empty, every node that can be reached was expanded, so I return False. Each node and each edge is handled a constant number of times, so the time is
O(V + E), and the space isO(V + E)for the lists, seen and the queue."
Complexity & Mathematical Proof
O(V + E)
Look at the code: for u, v in edges: reads each of the E edges once and does two appends. A node enters queue only when it is not in seen, and it joins seen in the same step, so each of the V nodes is added at most once and popped at most once. When a node is popped, for neighbour in graph[node]: reads its list, and the lists together hold 2E entries. Total O(V + E).
O(V + E)
graph holds 2E entries for V nodes, which is O(V + E). seen and queue each hold at most V nodes, which is O(V). Total O(V + E). The loop is not recursive, so the call stack is O(1).
T(V, E) = E (build lists) + V (pushes) + V (pops) + 2E (neighbour reads) = O(V + E)
Derivation Progression
for u, v in edges: graph[u].append(v); graph[v].append(u) → E steps
Each edge is read once and stored in both directions, which is 2 appends.
seen.add(neighbour); queue.append(neighbour) → at most V pushes and V pops
A node joins queue only if it is not in seen, and it joins seen in the same step, so no node is pushed twice.
for neighbour in graph[node] → 2E reads over all pops
The neighbour lists hold 2E entries together, and each list is read once, when its node is popped.
Variable Definitions
Number of nodes in the graph (n)
Number of edges, len(edges)
Memory Architecture & Bounds
O(1): no recursion
O(V + E): graph holds 2E entries; seen and queue hold at most V nodes each
O(1): one boolean
Boundary Best / Worst Cases
when source is destination, and otherwise because the lists are always built first
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "edges" that join two nodes, and the question whether "a valid path from source to destination" exists: reachability in an undirected graph, so BFS with a seen set. At scale the same traversal answers whether two machines are in the same network segment.
nodes and edges. One pass over the nodes and the edges is , about steps. A recursive DFS can go calls deep, which is more than Python's default call stack allows, so the loop with queue is also the safe choice here.
Skipping the check if neighbour not in seen: lets the nodes of a cycle refill queue, and the loop never ends when destination cannot be reached. Adding only one direction of each edge hides every path that starts at the other end. Marking a node when it leaves queue is correct but slow: on a complete graph of 10 nodes, queue receives 45 pushes instead of 9.
Find if Path Exists in Graph (LeetCode 1971)
A graph has n nodes, numbered from 0 to n - 1. The list edges describes its connections. Each pair [u, v] is one edge, and it joins node u and node v in both directions, so you can walk it either way.
You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.
Worked Examples
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2truen = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5false⚖️Formal Constraints & Bounds
1 <= n <= 2 * 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ui, vi <= n - 1ui != vi0 <= source, destination <= n - 1There are no duplicate edges.
There are no self-edges.
Core Insight
Mark a node in seen at the moment it is added to queue: a node with two parents is then queued once, and a cycle cannot refill the queue, so the loop always ends.
Real-World Scenario & Production Applications
Checking whether one computer can send data to another computer in a network, or whether one station can reach another station on a railway map, is the same question.
Step-by-Step Execution Trace Table
Step-by-Step Decision Trace (Example 2)
- Step 1 (source is not destination):
source = 0anddestination = 5are different nodes, so a search is needed. - Step 2 (build
graph): every edge is stored in both directions.graph = {0: [1, 2], 1: [0], 2: [0], 3: [5, 4], 5: [3, 4], 4: [5, 3]}. - Step 3 (start):
seen = {0}andqueue = [0]. The source is marked before the loop starts. - Step 4 (pop 0):
node = 0. Neighbour1is not the destination and is not inseen, soseen = {0, 1}andqueue = [1]. Neighbour2is new too, soseen = {0, 1, 2}andqueue = [1, 2]. - Step 5 (pop 1):
node = 1. Its only neighbour is0. Node0is already inseen, so it is not queued again. - Step 6 (pop 2):
node = 2. Its only neighbour is0, which is already inseen. Nothing is queued. - Step 7 (empty queue):
queue = []. Every node that can be reached from node 0 was expanded, and none of them is node 5.
Search complete: return False.
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2Expected:true| 1 | if source == destination: return True |
| 2 | graph = lists of neighbours, built from edges (both directions) |
| 3 | seen = {source} |
| 4 | queue = deque([source]) |
| 5 | while queue: |
| 6 | node = queue.popleft() |
| 7 | for neighbour in graph[node]: |
| 8 | if neighbour == destination: return True |
| 9 | if neighbour not in seen: |
| 10 | seen.add(neighbour) |
| 11 | queue.append(neighbour) |
| 12 | return False |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A graph is a set of nodes joined by edges. In a tree, every node has one parent. In a graph, one node can be reached from two parents, and the edges can form a cycle. A cycle is a path that comes back to the node where it started.
Breadth-first search (BFS) on a graph uses the same queue as level-order traversal. It adds one rule: a set named seen records every node that has been added to queue. A node that is already in seen is never added again.
🚆 Real-World Example: Train Stations
Each station is a node and each track between two stations is an edge. You start at one station and want to know whether you can reach another station. You keep a list of the stations that you have already planned to visit. Before you plan a station, you check the list. Without the list, two tracks that lead to the same station, or a loop of tracks, would put the same station in your plan again and again.
🔑 Why It Works
seen.add(neighbour) runs in the same step as queue.append(neighbour). A node that waits in queue is therefore already marked, so a second parent cannot add it again. Each node enters queue once, so the loop runs at most n times and ends even when the graph has a cycle.
Adding a node without checking
seen: A graph can have a cycle. Without the check, every neighbour goes intoqueueagain and again, so the loop never ends whendestinationcannot be reached. Add a node toseenat the moment it joinsqueue.Adding only one direction of each edge: An edge
[u, v]joins both nodes. Addvto the neighbours ofuanduto the neighbours ofv, or a search that starts atvfinds no neighbour.Skipping the case
source == destination: A path of length 0 exists, even whenedgesis empty. ReturnTruebefore the search starts.Marking a node when it leaves
queueinstead of when it joins: A node that waits inqueueis not yet inseen, so a second parent adds it again and the same node is expanded many times.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement gives n nodes and a list of two-way edges, and asks whether destination can be "reached" from source. The input is a graph that can have cycles, and the search starts from one node. That is Graph BFS with a seen set.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every node in seen is in queue or has already left it, so each node is added to queue exactly once. The decision: a neighbour that is not in seen joins seen and queue together, and a neighbour that is already in seen is skipped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use BFS with a seen set. If source is destination, I return True at once. Otherwise I build a list of neighbours for each node from the edges, adding each edge in both directions, because it can be walked either way. I mark source in seen, put it in the queue, and repeat: take the oldest node, and look at each of its neighbours. If a neighbour is the destination, I return True. If it is not in seen, I add it to seen and to the queue in the same step. So every node waits in the queue at most once, a node with two parents is expanded once, and a cycle cannot keep the loop running. If the queue becomes empty, every node that can be reached was expanded, so I return False. Each node and each edge is handled a constant number of times, so the time is
O(V + E), and the space isO(V + E)for the lists, seen and the queue."
Complexity & Mathematical Proof
O(V + E)
Look at the code: for u, v in edges: reads each of the E edges once and does two appends. A node enters queue only when it is not in seen, and it joins seen in the same step, so each of the V nodes is added at most once and popped at most once. When a node is popped, for neighbour in graph[node]: reads its list, and the lists together hold 2E entries. Total O(V + E).
O(V + E)
graph holds 2E entries for V nodes, which is O(V + E). seen and queue each hold at most V nodes, which is O(V). Total O(V + E). The loop is not recursive, so the call stack is O(1).
T(V, E) = E (build lists) + V (pushes) + V (pops) + 2E (neighbour reads) = O(V + E)
Derivation Progression
for u, v in edges: graph[u].append(v); graph[v].append(u) → E steps
Each edge is read once and stored in both directions, which is 2 appends.
seen.add(neighbour); queue.append(neighbour) → at most V pushes and V pops
A node joins queue only if it is not in seen, and it joins seen in the same step, so no node is pushed twice.
for neighbour in graph[node] → 2E reads over all pops
The neighbour lists hold 2E entries together, and each list is read once, when its node is popped.
Variable Definitions
Number of nodes in the graph (n)
Number of edges, len(edges)
Memory Architecture & Bounds
O(1): no recursion
O(V + E): graph holds 2E entries; seen and queue hold at most V nodes each
O(1): one boolean
Boundary Best / Worst Cases
when source is destination, and otherwise because the lists are always built first
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "edges" that join two nodes, and the question whether "a valid path from source to destination" exists: reachability in an undirected graph, so BFS with a seen set. At scale the same traversal answers whether two machines are in the same network segment.
nodes and edges. One pass over the nodes and the edges is , about steps. A recursive DFS can go calls deep, which is more than Python's default call stack allows, so the loop with queue is also the safe choice here.
Skipping the check if neighbour not in seen: lets the nodes of a cycle refill queue, and the loop never ends when destination cannot be reached. Adding only one direction of each edge hides every path that starts at the other end. Marking a node when it leaves queue is correct but slow: on a complete graph of 10 nodes, queue receives 45 pushes instead of 9.