What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Breadth-First Search (BFS)

Builds on Level-Order BFS, which you haven’t finished yet.

P2EasyBuilt on Level-Order BFS~5 min speedrun

BFS on a Graph (Mark on Push)

Built on

Level-Order BFSA seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.

Grows into

Shortest-Path BFS

The problem

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

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.

Example 1

Input:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output:true

Two paths lead from node 0 to node 2. One is 0 -> 1 -> 2. The other is 0 -> 2, which uses the edge [2, 0] in the direction from 0 to 2.

Graph BFS

graph with cycles ➔ mark `seen` when pushed ➔ each node queued once

Spot it when: The input is a graph given as edges or adjacency lists, it can have cycles, and you must reach, find or visit nodes starting from one node.

Graph BFS

Python

1	from collections import defaultdict, deque
2	from typing import Dict, List
3
4	def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
5	"""Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue.
6	V = n nodes. E = len(edges). The graph is undirected and can have cycles.
7	Time: O(V + E) \| Space: O(V + E) for the adjacency lists, seen and queue
8	"""
9	if source == destination:
10	return True
11
12	graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list
13	for u, v in edges:
14	graph[u].append(v)
15	graph[v].append(u)
16
17	seen = {source} # every node that is in queue or has already left it
18	queue = deque([source]) # nodes found but not yet expanded, in the order they were found
19
20	while queue:
21	# 1. Expand the Oldest Found Node:
22	# Every neighbour of node is looked at once, when node leaves queue.
23	node = queue.popleft()
24	for neighbour in graph[node]:
25	if neighbour == destination:
26	return True
27
28	# 2. Mark on Push:
29	# A neighbour joins seen at the moment it joins queue, not when it leaves.
30	# A node that waits in queue is then already marked, so a second parent
31	# cannot add it again, and a cycle cannot refill the queue.
32	if neighbour not in seen:
33	seen.add(neighbour)
34	queue.append(neighbour)
35
36	return False

Invariant: Every node in seen is in queue or has already left it, so each node is added to queue exactly once.

A graph can reach one node from two parents, so mark a node in seen at the moment you add it to queue, not when you take it out. Each node then enters queue once, so a cycle cannot refill the queue and the loop ends. The trap is skipping the seen check: on a cycle, the loop never ends when destination cannot be reached.

See it run

Mark on push, step by step

seen [0]destination 6

Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.

node the node just taken out of queue
queued waiting in queue, already in seen
expanded all its neighbours were looked at
neighbour the neighbour being looked at now

Put the source 0 in queue and in seen. The destination is 6.

queue

seen

1 / 17

Gotchas1 of 4

The trap
Gotcha 1: Adding a neighbour without checking seen
Mistake
```
queue.append(neighbour)
```
Fix
```
if neighbour not in seen:
    seen.add(neighbour)
    queue.append(neighbour)
```
What happens: A graph can have a cycle. Without the seen check, every neighbour goes into queue again and again. On a cycle the nodes keep refilling queue, so the loop never ends when the destination cannot be reached.
Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3
Mistake: the loop never endsFix: returns False
Gotcha 2: Adding only one direction of each edge
Mistake
```
graph[u].append(v)
```
Fix
```
graph[u].append(v)
graph[v].append(u)
```
What happens: An edge [u, v] joins both nodes. Adding v to the list of u only lets the search walk from u to v. A search that starts at v finds no neighbour.
Example: n = 2, edges = [[0,1]], source = 1, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 3: Skipping the check source == destination
Mistake
```
pass
```
Fix
```
if source == destination:
    return True
```
What happens: The search only compares a neighbour with destination. The source itself is never a neighbour of anything in this walk, so a path of length 0 is never found. The graph can even have no edges.
Example: n = 1, edges = [], source = 0, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 4: Marking a node when it leaves queue instead of when it joins
Mistake
```
node = queue.popleft()
seen.add(node)
```
Fix
```
seen.add(neighbour)
queue.append(neighbour)
```
What happens: A node that waits in queue is not yet in seen. A second parent finds it unmarked and adds it again. The answer stays correct. The code adds a node to seen only when it takes the node out of queue, and skips a node that is already in seen. Each parent still adds the node to queue before that. On a complete graph with 10 nodes, the queue receives 45 pushes instead of 9.

Not this one if…

The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no seen set is needed. See Level-Order BFS
You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores dist. See Shortest-Path BFS

Deep Dive

Why a graph needs `seen` and a tree does not

In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.

In a graph, a node can have two parents or sit on a cycle. In the board, node 3 is a neighbour of both 1 and 2. The walk reaches it from node 1 first. When it later looks at node 3 from node 2, node 3 is already in seen, so it is not added again.

The board uses source = 0 and destination = 6. Node 6 is in a separate group of nodes, so queue empties and the answer is False. seen ends as [0, 1, 2, 3, 4], and each of those nodes was added to queue once.

Mark on push: why the mark goes before `queue.append`

seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.

If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.

On a complete graph with 10 nodes, marking on push puts 9 nodes into queue. Marking on pop means the code adds a node to seen only when it takes the node out of queue, skips a node that is already in seen, and adds a neighbour to queue unless the neighbour is already in seen. Then queue gets 45 entries, one for each pair of nodes.

What happens with no `seen` at all

Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.

Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.

With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.

The cost, and what the card does not add

The code builds the adjacency lists in O(V + E) time. Each node enters queue once and leaves it once. Each link is looked at twice, once from each end. So the search takes O(V + E) time, and graph, seen and queue take O(V + E) space.

This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.

For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.

60-Second Pitch

"The graph is undirected and can have cycles, so I build adjacency lists and run BFS from the source. I keep a seen set and add a node to seen at the same moment I add it to queue. A node that is waiting in queue is then already marked, so a second parent cannot add it again, and a cycle cannot refill the queue. If a neighbour is the destination, I return True. If queue empties first, I return False. Each node enters queue once and each link is looked at twice, so the time is O(V + E) and the space is O(V + E)."

Common Questions

Why do you mark a node when you add it to queue and not when you take it out?: A node that is waiting in queue is not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.
Can you use depth-first search instead? What changes?: Yes, for this question. Replace queue.popleft() with stack.pop(), or use recursion. The seen rule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.
What are the time and space complexity?: O(V + E) time and O(V + E) space. Building the adjacency lists costs O(V + E). Each node enters queue once. Each link is looked at twice, once from each end.
What if the input is an adjacency matrix and not a list of edges?: Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The seen rule does not change.
How would you also count the nodes that can be reached?: Return len(seen) when queue is empty. seen holds exactly the nodes that were added to queue, which are the nodes reachable from the source.

SWE Reasoning

Spot it

The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
No weights and no order of visiting is required, so a plain queue is enough.
A node can be reached from two different parents. This is the signal that a seen set is needed.

The invariant, step by step

seen starts as {source} and queue starts as [source]. Both hold the source, so the invariant holds.
Each round takes the oldest node out of queue and looks at its neighbours.
A neighbour that is the destination ends the search with True.
A neighbour that is not in seen is added to seen and to queue in the same step. The invariant still holds.
A neighbour already in seen is left alone. It is in queue or already expanded.
When queue is empty, every node reachable from the source was expanded, so the answer is False.

Traps

No seen check. On a cycle, queue never empties when the destination cannot be reached.
Only one direction of each edge. The graph is undirected, so both graph[u] and graph[v] need the link.
No check for source == destination. The walk compares only neighbours, so a path of length 0 is missed.
Marking when the node leaves queue. A waiting node is not marked, so it is added again and expanded many times.

Practice

Canonical LeetCode:Find if Path Exists in Graph (LC 1971)Clone Graph (LC 133)Keys and Rooms (LC 841)Number of Provinces (LC 547)

Theory Context•Breadth-First Search (BFS)

Builds on Level-Order BFS, which you haven’t finished yet.

P2EasyBuilt on Level-Order BFS~5 min speedrun

BFS on a Graph (Mark on Push)

Built on

Level-Order BFSA seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.

Grows into

Shortest-Path BFS

The problem

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.

Example 1

Input:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output:true

Two paths lead from node 0 to node 2. One is 0 -> 1 -> 2. The other is 0 -> 2, which uses the edge [2, 0] in the direction from 0 to 2.

Graph BFS

graph with cycles ➔ mark `seen` when pushed ➔ each node queued once

Spot it when: The input is a graph given as edges or adjacency lists, it can have cycles, and you must reach, find or visit nodes starting from one node.

Graph BFS

Python

1	from collections import defaultdict, deque
2	from typing import Dict, List
3
4	def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
5	"""Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue.
6	V = n nodes. E = len(edges). The graph is undirected and can have cycles.
7	Time: O(V + E) \| Space: O(V + E) for the adjacency lists, seen and queue
8	"""
9	if source == destination:
10	return True
11
12	graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list
13	for u, v in edges:
14	graph[u].append(v)
15	graph[v].append(u)
16
17	seen = {source} # every node that is in queue or has already left it
18	queue = deque([source]) # nodes found but not yet expanded, in the order they were found
19
20	while queue:
21	# 1. Expand the Oldest Found Node:
22	# Every neighbour of node is looked at once, when node leaves queue.
23	node = queue.popleft()
24	for neighbour in graph[node]:
25	if neighbour == destination:
26	return True
27
28	# 2. Mark on Push:
29	# A neighbour joins seen at the moment it joins queue, not when it leaves.
30	# A node that waits in queue is then already marked, so a second parent
31	# cannot add it again, and a cycle cannot refill the queue.
32	if neighbour not in seen:
33	seen.add(neighbour)
34	queue.append(neighbour)
35
36	return False

Invariant: Every node in seen is in queue or has already left it, so each node is added to queue exactly once.

See it run

Mark on push, step by step

seen [0]destination 6

Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.

node the node just taken out of queue
queued waiting in queue, already in seen
expanded all its neighbours were looked at
neighbour the neighbour being looked at now

Put the source 0 in queue and in seen. The destination is 6.

queue

seen

1 / 17

Gotchas1 of 4

The trap
Gotcha 1: Adding a neighbour without checking seen
Mistake
```
queue.append(neighbour)
```
Fix
```
if neighbour not in seen:
    seen.add(neighbour)
    queue.append(neighbour)
```
What happens: A graph can have a cycle. Without the seen check, every neighbour goes into queue again and again. On a cycle the nodes keep refilling queue, so the loop never ends when the destination cannot be reached.
Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3
Mistake: the loop never endsFix: returns False
Gotcha 2: Adding only one direction of each edge
Mistake
```
graph[u].append(v)
```
Fix
```
graph[u].append(v)
graph[v].append(u)
```
What happens: An edge [u, v] joins both nodes. Adding v to the list of u only lets the search walk from u to v. A search that starts at v finds no neighbour.
Example: n = 2, edges = [[0,1]], source = 1, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 3: Skipping the check source == destination
Mistake
```
pass
```
Fix
```
if source == destination:
    return True
```
What happens: The search only compares a neighbour with destination. The source itself is never a neighbour of anything in this walk, so a path of length 0 is never found. The graph can even have no edges.
Example: n = 1, edges = [], source = 0, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 4: Marking a node when it leaves queue instead of when it joins
Mistake
```
node = queue.popleft()
seen.add(node)
```
Fix
```
seen.add(neighbour)
queue.append(neighbour)
```
What happens: A node that waits in queue is not yet in seen. A second parent finds it unmarked and adds it again. The answer stays correct. The code adds a node to seen only when it takes the node out of queue, and skips a node that is already in seen. Each parent still adds the node to queue before that. On a complete graph with 10 nodes, the queue receives 45 pushes instead of 9.

Not this one if…

The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no seen set is needed. See Level-Order BFS
You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores dist. See Shortest-Path BFS

Deep Dive

Why a graph needs `seen` and a tree does not

In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.

Mark on push: why the mark goes before `queue.append`

seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.

If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.

What happens with no `seen` at all

Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.

Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.

With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.

The cost, and what the card does not add

This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.

For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.

60-Second Pitch

Common Questions

Why do you mark a node when you add it to queue and not when you take it out?: A node that is waiting in queue is not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.
Can you use depth-first search instead? What changes?: Yes, for this question. Replace queue.popleft() with stack.pop(), or use recursion. The seen rule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.
What are the time and space complexity?: O(V + E) time and O(V + E) space. Building the adjacency lists costs O(V + E). Each node enters queue once. Each link is looked at twice, once from each end.
What if the input is an adjacency matrix and not a list of edges?: Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The seen rule does not change.
How would you also count the nodes that can be reached?: Return len(seen) when queue is empty. seen holds exactly the nodes that were added to queue, which are the nodes reachable from the source.

SWE Reasoning

Spot it

The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
No weights and no order of visiting is required, so a plain queue is enough.
A node can be reached from two different parents. This is the signal that a seen set is needed.

The invariant, step by step

seen starts as {source} and queue starts as [source]. Both hold the source, so the invariant holds.
Each round takes the oldest node out of queue and looks at its neighbours.
A neighbour that is the destination ends the search with True.
A neighbour that is not in seen is added to seen and to queue in the same step. The invariant still holds.
A neighbour already in seen is left alone. It is in queue or already expanded.
When queue is empty, every node reachable from the source was expanded, so the answer is False.

Traps

No seen check. On a cycle, queue never empties when the destination cannot be reached.
Only one direction of each edge. The graph is undirected, so both graph[u] and graph[v] need the link.
No check for source == destination. The walk compares only neighbours, so a path of length 0 is missed.
Marking when the node leaves queue. A waiting node is not marked, so it is added again and expanded many times.

Practice

Canonical LeetCode:Find if Path Exists in Graph (LC 1971)Clone Graph (LC 133)Keys and Rooms (LC 841)Number of Provinces (LC 547)

Theory Context•Breadth-First Search (BFS)

Builds on Level-Order BFS, which you haven’t finished yet.

P2EasyBuilt on Level-Order BFS~5 min speedrun

BFS on a Graph (Mark on Push)

Built on

Level-Order BFSA seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.

Grows into

Shortest-Path BFS

The problem

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.

Example 1

Input:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output:true

Two paths lead from node 0 to node 2. One is 0 -> 1 -> 2. The other is 0 -> 2, which uses the edge [2, 0] in the direction from 0 to 2.

Graph BFS

graph with cycles ➔ mark `seen` when pushed ➔ each node queued once

Spot it when: The input is a graph given as edges or adjacency lists, it can have cycles, and you must reach, find or visit nodes starting from one node.

Graph BFS

Python

1	from collections import defaultdict, deque
2	from typing import Dict, List
3
4	def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
5	"""Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue.
6	V = n nodes. E = len(edges). The graph is undirected and can have cycles.
7	Time: O(V + E) \| Space: O(V + E) for the adjacency lists, seen and queue
8	"""
9	if source == destination:
10	return True
11
12	graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list
13	for u, v in edges:
14	graph[u].append(v)
15	graph[v].append(u)
16
17	seen = {source} # every node that is in queue or has already left it
18	queue = deque([source]) # nodes found but not yet expanded, in the order they were found
19
20	while queue:
21	# 1. Expand the Oldest Found Node:
22	# Every neighbour of node is looked at once, when node leaves queue.
23	node = queue.popleft()
24	for neighbour in graph[node]:
25	if neighbour == destination:
26	return True
27
28	# 2. Mark on Push:
29	# A neighbour joins seen at the moment it joins queue, not when it leaves.
30	# A node that waits in queue is then already marked, so a second parent
31	# cannot add it again, and a cycle cannot refill the queue.
32	if neighbour not in seen:
33	seen.add(neighbour)
34	queue.append(neighbour)
35
36	return False

Invariant: Every node in seen is in queue or has already left it, so each node is added to queue exactly once.

See it run

Mark on push, step by step

seen [0]destination 6

Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.

node the node just taken out of queue
queued waiting in queue, already in seen
expanded all its neighbours were looked at
neighbour the neighbour being looked at now

Put the source 0 in queue and in seen. The destination is 6.

queue

seen

1 / 17

Gotchas1 of 4

The trap
Gotcha 1: Adding a neighbour without checking seen
Mistake
```
queue.append(neighbour)
```
Fix
```
if neighbour not in seen:
    seen.add(neighbour)
    queue.append(neighbour)
```
What happens: A graph can have a cycle. Without the seen check, every neighbour goes into queue again and again. On a cycle the nodes keep refilling queue, so the loop never ends when the destination cannot be reached.
Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3
Mistake: the loop never endsFix: returns False
Gotcha 2: Adding only one direction of each edge
Mistake
```
graph[u].append(v)
```
Fix
```
graph[u].append(v)
graph[v].append(u)
```
What happens: An edge [u, v] joins both nodes. Adding v to the list of u only lets the search walk from u to v. A search that starts at v finds no neighbour.
Example: n = 2, edges = [[0,1]], source = 1, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 3: Skipping the check source == destination
Mistake
```
pass
```
Fix
```
if source == destination:
    return True
```
What happens: The search only compares a neighbour with destination. The source itself is never a neighbour of anything in this walk, so a path of length 0 is never found. The graph can even have no edges.
Example: n = 1, edges = [], source = 0, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 4: Marking a node when it leaves queue instead of when it joins
Mistake
```
node = queue.popleft()
seen.add(node)
```
Fix
```
seen.add(neighbour)
queue.append(neighbour)
```
What happens: A node that waits in queue is not yet in seen. A second parent finds it unmarked and adds it again. The answer stays correct. The code adds a node to seen only when it takes the node out of queue, and skips a node that is already in seen. Each parent still adds the node to queue before that. On a complete graph with 10 nodes, the queue receives 45 pushes instead of 9.

Not this one if…

The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no seen set is needed. See Level-Order BFS
You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores dist. See Shortest-Path BFS

Deep Dive

Why a graph needs `seen` and a tree does not

In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.

Mark on push: why the mark goes before `queue.append`

seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.

If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.

What happens with no `seen` at all

Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.

Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.

With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.

The cost, and what the card does not add

This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.

For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.

60-Second Pitch

Common Questions

Why do you mark a node when you add it to queue and not when you take it out?: A node that is waiting in queue is not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.
Can you use depth-first search instead? What changes?: Yes, for this question. Replace queue.popleft() with stack.pop(), or use recursion. The seen rule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.
What are the time and space complexity?: O(V + E) time and O(V + E) space. Building the adjacency lists costs O(V + E). Each node enters queue once. Each link is looked at twice, once from each end.
What if the input is an adjacency matrix and not a list of edges?: Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The seen rule does not change.
How would you also count the nodes that can be reached?: Return len(seen) when queue is empty. seen holds exactly the nodes that were added to queue, which are the nodes reachable from the source.

SWE Reasoning

Spot it

The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
No weights and no order of visiting is required, so a plain queue is enough.
A node can be reached from two different parents. This is the signal that a seen set is needed.

The invariant, step by step

seen starts as {source} and queue starts as [source]. Both hold the source, so the invariant holds.
Each round takes the oldest node out of queue and looks at its neighbours.
A neighbour that is the destination ends the search with True.
A neighbour that is not in seen is added to seen and to queue in the same step. The invariant still holds.
A neighbour already in seen is left alone. It is in queue or already expanded.
When queue is empty, every node reachable from the source was expanded, so the answer is False.

Traps

No seen check. On a cycle, queue never empties when the destination cannot be reached.
Only one direction of each edge. The graph is undirected, so both graph[u] and graph[v] need the link.
No check for source == destination. The walk compares only neighbours, so a path of length 0 is missed.
Marking when the node leaves queue. A waiting node is not marked, so it is added again and expanded many times.

Practice

Canonical LeetCode:Find if Path Exists in Graph (LC 1971)Clone Graph (LC 133)Keys and Rooms (LC 841)Number of Provinces (LC 547)

Theory Context•Breadth-First Search (BFS)

Builds on Level-Order BFS, which you haven’t finished yet.

P2EasyBuilt on Level-Order BFS~5 min speedrun

BFS on a Graph (Mark on Push)

Built on

Level-Order BFSA seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.

Grows into

Shortest-Path BFS

The problem

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.

Example 1

Input:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output:true

Two paths lead from node 0 to node 2. One is 0 -> 1 -> 2. The other is 0 -> 2, which uses the edge [2, 0] in the direction from 0 to 2.

Graph BFS

graph with cycles ➔ mark `seen` when pushed ➔ each node queued once

Spot it when: The input is a graph given as edges or adjacency lists, it can have cycles, and you must reach, find or visit nodes starting from one node.

Graph BFS

Python

1	from collections import defaultdict, deque
2	from typing import Dict, List
3
4	def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
5	"""Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue.
6	V = n nodes. E = len(edges). The graph is undirected and can have cycles.
7	Time: O(V + E) \| Space: O(V + E) for the adjacency lists, seen and queue
8	"""
9	if source == destination:
10	return True
11
12	graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list
13	for u, v in edges:
14	graph[u].append(v)
15	graph[v].append(u)
16
17	seen = {source} # every node that is in queue or has already left it
18	queue = deque([source]) # nodes found but not yet expanded, in the order they were found
19
20	while queue:
21	# 1. Expand the Oldest Found Node:
22	# Every neighbour of node is looked at once, when node leaves queue.
23	node = queue.popleft()
24	for neighbour in graph[node]:
25	if neighbour == destination:
26	return True
27
28	# 2. Mark on Push:
29	# A neighbour joins seen at the moment it joins queue, not when it leaves.
30	# A node that waits in queue is then already marked, so a second parent
31	# cannot add it again, and a cycle cannot refill the queue.
32	if neighbour not in seen:
33	seen.add(neighbour)
34	queue.append(neighbour)
35
36	return False

Invariant: Every node in seen is in queue or has already left it, so each node is added to queue exactly once.

See it run

Mark on push, step by step

seen [0]destination 6

Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.

node the node just taken out of queue
queued waiting in queue, already in seen
expanded all its neighbours were looked at
neighbour the neighbour being looked at now

Put the source 0 in queue and in seen. The destination is 6.

queue

seen

1 / 17

Gotchas1 of 4

The trap
Gotcha 1: Adding a neighbour without checking seen
Mistake
```
queue.append(neighbour)
```
Fix
```
if neighbour not in seen:
    seen.add(neighbour)
    queue.append(neighbour)
```
What happens: A graph can have a cycle. Without the seen check, every neighbour goes into queue again and again. On a cycle the nodes keep refilling queue, so the loop never ends when the destination cannot be reached.
Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3
Mistake: the loop never endsFix: returns False
Gotcha 2: Adding only one direction of each edge
Mistake
```
graph[u].append(v)
```
Fix
```
graph[u].append(v)
graph[v].append(u)
```
What happens: An edge [u, v] joins both nodes. Adding v to the list of u only lets the search walk from u to v. A search that starts at v finds no neighbour.
Example: n = 2, edges = [[0,1]], source = 1, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 3: Skipping the check source == destination
Mistake
```
pass
```
Fix
```
if source == destination:
    return True
```
What happens: The search only compares a neighbour with destination. The source itself is never a neighbour of anything in this walk, so a path of length 0 is never found. The graph can even have no edges.
Example: n = 1, edges = [], source = 0, destination = 0
Mistake: returns FalseFix: returns True
Gotcha 4: Marking a node when it leaves queue instead of when it joins
Mistake
```
node = queue.popleft()
seen.add(node)
```
Fix
```
seen.add(neighbour)
queue.append(neighbour)
```
What happens: A node that waits in queue is not yet in seen. A second parent finds it unmarked and adds it again. The answer stays correct. The code adds a node to seen only when it takes the node out of queue, and skips a node that is already in seen. Each parent still adds the node to queue before that. On a complete graph with 10 nodes, the queue receives 45 pushes instead of 9.

Not this one if…

The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no seen set is needed. See Level-Order BFS
You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores dist. See Shortest-Path BFS

Deep Dive

Why a graph needs `seen` and a tree does not

In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.

Mark on push: why the mark goes before `queue.append`

seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.

If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.

What happens with no `seen` at all

Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.

Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.

With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.

The cost, and what the card does not add

This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.

For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.

60-Second Pitch

Common Questions

Why do you mark a node when you add it to queue and not when you take it out?: A node that is waiting in queue is not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.
Can you use depth-first search instead? What changes?: Yes, for this question. Replace queue.popleft() with stack.pop(), or use recursion. The seen rule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.
What are the time and space complexity?: O(V + E) time and O(V + E) space. Building the adjacency lists costs O(V + E). Each node enters queue once. Each link is looked at twice, once from each end.
What if the input is an adjacency matrix and not a list of edges?: Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The seen rule does not change.
How would you also count the nodes that can be reached?: Return len(seen) when queue is empty. seen holds exactly the nodes that were added to queue, which are the nodes reachable from the source.

SWE Reasoning

Spot it

The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
No weights and no order of visiting is required, so a plain queue is enough.
A node can be reached from two different parents. This is the signal that a seen set is needed.

The invariant, step by step

seen starts as {source} and queue starts as [source]. Both hold the source, so the invariant holds.
Each round takes the oldest node out of queue and looks at its neighbours.
A neighbour that is the destination ends the search with True.
A neighbour that is not in seen is added to seen and to queue in the same step. The invariant still holds.
A neighbour already in seen is left alone. It is in queue or already expanded.
When queue is empty, every node reachable from the source was expanded, so the answer is False.

Traps

No seen check. On a cycle, queue never empties when the destination cannot be reached.
Only one direction of each edge. The graph is undirected, so both graph[u] and graph[v] need the link.
No check for source == destination. The walk compares only neighbours, so a path of length 0 is missed.
Marking when the node leaves queue. A waiting node is not marked, so it is added again and expanded many times.

Practice

Canonical LeetCode:Find if Path Exists in Graph (LC 1971)Clone Graph (LC 133)Keys and Rooms (LC 841)Number of Provinces (LC 547)

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

Graph BFS

See it run

Deep Dive

Why a graph needs seen and a tree does not

Mark on push: why the mark goes before queue.append

What happens with no seen at all

The cost, and what the card does not add

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

Graph BFS

See it run

Deep Dive

Why a graph needs seen and a tree does not

Mark on push: why the mark goes before queue.append

What happens with no seen at all

The cost, and what the card does not add

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

Graph BFS

See it run

Deep Dive

Why a graph needs seen and a tree does not

Mark on push: why the mark goes before queue.append

What happens with no seen at all

The cost, and what the card does not add

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Find if Path Exists in Graph (LC 1971)(opens leetcode.com)

Graph BFS

See it run

Deep Dive

Why a graph needs seen and a tree does not

Mark on push: why the mark goes before queue.append

What happens with no seen at all

The cost, and what the card does not add

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Why a graph needs `seen` and a tree does not

Mark on push: why the mark goes before `queue.append`

What happens with no `seen` at all

Why a graph needs `seen` and a tree does not

Mark on push: why the mark goes before `queue.append`

What happens with no `seen` at all

Why a graph needs `seen` and a tree does not

Mark on push: why the mark goes before `queue.append`

What happens with no `seen` at all

Why a graph needs `seen` and a tree does not

Mark on push: why the mark goes before `queue.append`

What happens with no `seen` at all