Abstract / Summary

Check if a path exists between two nodes in a directed graph.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (1+ million submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether a path exists between two vertices in an undirected graph. It receives the number of vertices, a list of edge pairs, a source vertex, and a destination vertex, and returns a Boolean indicating connectivity. The algorithm builds an adjacency list, then performs an iterative depth-first search (DFS) using an explicit stack. Early termination occurs as soon as the destination is reached.

Graph Construction

The first logical block creates a list of empty neighbor collections, one for each vertex, and then populates it with bidirectional connections derived from the edge list.

connect = [ [] for _ in range(n) ]
for a, b in edges:
    connect[a].append(b)
    connect[b].append(a)

By allocating a list of size n up front, the code guarantees constant-time access to any vertex’s neighbor list. The double insertion inside the loop reflects the undirected nature of the graph, ensuring that traversal can move in either direction along each edge.

Initialization of Search State

Before entering the search loop, the algorithm prepares a stack containing the source vertex and a Boolean array that tracks visited vertices.

todo = [ source ]
seen = [ False ] * n

The stack (todo) enables a LIFO order, which naturally yields a depth-first exploration. The seen array provides O(1) checks for whether a vertex has already been processed, preventing redundant work.

Iterative Depth-First Search

The core of the solution is a while loop that continues until the stack is empty. In each iteration, the top element is removed, compared to the destination, and, if not yet visited, its neighbors are added to the stack.

while todo:
    pos = todo.pop()
    if pos == destination:
        return True

    if seen[pos]:
        continue
    seen[pos] = True

    todo.extend(connect[pos])

The pop operation retrieves the most recently discovered vertex, preserving the depth-first order. The immediate equality test allows the function to exit as soon as the destination is encountered, avoiding unnecessary exploration. The guard if seen[pos] skips vertices that have already been processed, which can happen because neighbors are added without checking visitation status. Marking a vertex as seen only after the equality test ensures that the source-equals-destination case is handled correctly.

Edge Cases Handled

When the source and destination are the same vertex, the first pop yields the source, the equality condition succeeds, and the function returns True without further work. If the graph contains isolated vertices or components disconnected from the source, the stack eventually empties, and the function returns False. Duplicate edges or self-loops are accommodated because each insertion simply appends to the adjacency list; the visitation guard prevents infinite loops that could arise from self-loops. An empty edge list results in an adjacency structure with only empty neighbor lists, and the search proceeds correctly based on the source-destination relationship.

Performance Optimizations

The adjacency list representation minimizes memory overhead compared to a matrix, especially for sparse graphs. Using a pre-allocated list for seen enables constant-time checks and updates. The iterative DFS avoids the overhead of recursive calls and the risk of stack overflow on deep graphs. Early termination on reaching the destination reduces the number of processed vertices in favorable cases. Adding all neighbors at once with extend reduces the number of individual push operations onto the stack. The algorithm also avoids unnecessary creation of auxiliary data structures beyond the adjacency list, the stack, and the visited array.

Imagine you are playing with a giant map of colorful houses connected by winding garden paths. Each house has a number so you can find it easily.

First, the computer makes a list to remember which houses are connected to each other by those paths. It looks at every path and writes down that if you can go from house a to house b, you can also go back from house b to house a.

Next, the computer needs a plan to find the way from the starting house to the destination house. It picks up a crayon and marks the starting house as a place to visit. It also keeps a small notepad to remember which houses have already been checked so it does not go in circles.

The computer keeps picking a house from its list to visit. If that house is the destination, the job is finished. If the house has already been visited, the computer ignores it and moves to the next one. Otherwise, it marks that house as visited so it knows it has been there. Then, it looks at all the paths leading away from that house and adds those new houses to its list of places to check.

It keeps doing this over and over again, hopping from path to path, until it either arrives at the destination house or runs out of paths to explore.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	Java	C++							TS
	WalkCCC	Python	Java	C++
	leetcode.ca	Python	Java	C++					Go	Rust	TS
	Progiez	Python	Java	C++
github	black-shadows			C++
	chandansgowda	Python
	charles-wangkai		Java
	everthis				JS
	fartem						Ruby
	fsq			C++
	JoshCrozier				JS
	lkwq007	Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn	Python
	varunu28		Java
	vthwang		Java
	yuanliu666							Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality