Problem overview
The method validPath receives the number of vertices n, a list of edges, a source vertex and a destination vertex. Vertices are labeled 0 to n - 1. Each edge [u, v] connects two vertices and works in both directions. The method returns true when you can walk from source to destination along edges, and false otherwise. No vertex has an edge to itself, and no pair of vertices is joined by more than one edge.
In the first example, n = 3 and the edges form a triangle: [[0, 1], [1, 2], [2, 0]]. From 0 you can go straight to 2, or through 1, so the answer is true. In the second example, n = 6 and the vertices split into two groups: 0, 1 and 2 on one side, and 3, 4 and 5 on the other. There is no path from 0 to 5, so the answer is false.
Approach: explore everything reachable from the source
A path exists exactly when destination belongs to the set of vertices reachable from source. So instead of searching for a path to one particular vertex, compute the whole reachable set and check whether the destination is in it.
Depth-first search (DFS) does that. Starting at the source, it marks the current vertex as visited, then visits each unvisited neighbor in turn, going as deep as possible down one branch before coming back. Marking vertices is what keeps the search finite: edges here form cycles (the triangle in the first example), and without the marks the search would walk around a cycle forever.
Edges arrive as a flat list, which is slow to search: finding the neighbors of one vertex would mean scanning every edge. So the first job is to turn the list into an adjacency list: an array where position i holds the list of vertices adjacent to vertex i. Because the graph is bi-directional, each edge is stored twice, once for each endpoint.
Step by step
- Create the adjacency list.
Array.from({length: n}, () => [])builds an array ofnslots and runs the function once per slot, so each vertex gets its own empty array. - Create a
Setnamedvisited. A set answers "have I seen this vertex?" in constant time on average. - Loop over
edgeswithfor (const edge of edges). Each edge is a pair whose two endpoints areedge[0]andedge[1]. - Record the first direction. Push
edge[1]ontograph[edge[0]]. - Record the second direction. Push
edge[0]ontograph[edge[1]]. Without this line the graph would be directed, and the search would miss paths that follow an edge backwards. - Run the search by calling
this.dfs(source, graph, visited). When it returns,visitedholds every vertex reachable from the source. - Return
visited.has(destination). ASetuseshas, notincludesas arrays do. - Define
dfs(node, graph, visited). The structures are passed along as arguments, so every recursive call reads and updates the same ones. - Mark first. Add
nodetovisitedbefore looking at its neighbors. A neighbor that leads back to this vertex will then find it already visited. - Loop over
graph[node]withfor (const adjacentNode of graph[node]). - Recurse only on unvisited neighbors. If
!visited.has(adjacentNode), callthis.dfson it with the samegraphandvisited.
On the second example, the search from 0 marks 0, goes to 1 (a dead end), then to 2 (also a dead end), and returns. The visited set is {0, 1, 2}, which does not contain 5, so the result is false.
The solution in JavaScript
class Solution {
validPath(n, edges, source, destination) {
const graph = Array.from({length: n}, () => []);
const visited = new Set();
for (const edge of edges) {
graph[edge[0]].push(edge[1]);
graph[edge[1]].push(edge[0]);
}
this.dfs(source, graph, visited);
return visited.has(destination);
}
dfs(node, graph, visited) {
visited.add(node);
for (const adjacentNode of graph[node]) {
if (!visited.has(adjacentNode)) {
this.dfs(adjacentNode, graph, visited);
}
}
}
}
JavaScript details worth knowing:
Array.fromversusfill.new Array(n).fill([])puts the same array object in every slot, so pushing a neighbor for vertex 0 would also add it for every other vertex.Array.from({length: n}, () => [])calls the function again for each slot and creates separate arrays.- Sets and objects. A
Setstores values of any type and keeps no duplicates.addinserts a value, andhastests membership. Adding the same vertex twice changes nothing. - Shared state through references. Arrays and sets are objects, so passing them to
dfspasses a reference. All the recursive calls work on the samevisited, which is whydfsneeds no return value. - Calling methods with
this.dfsis a method of the class, so it must be called asthis.dfs(...), both fromvalidPathand from itself. - The unused parameter. The recursion never reads
nafter the adjacency list is built. It is only needed to size the list.
Complexity
Let V be the number of vertices and E the number of edges.
Time: O(V + E). Building the list touches each edge once. The search marks each vertex once, and when it visits a vertex it looks at each of its neighbors once. Over the whole search that is each edge twice, once from each endpoint.
Space: O(V + E). The adjacency list holds every edge twice and has one slot per vertex. The set holds at most V vertices, and the recursion stack can be as deep as V.
That last point deserves a warning for large inputs. The statement allows up to 200,000 vertices. For a graph shaped like a single long path, the recursion goes one call deeper per vertex, and a chain of 200,000 vertices overflows the call stack in Node, which throws a RangeError (Maximum call stack size exceeded). Typical small and medium tests pass, but a stack-based loop or a queue-based BFS avoids the limit.
Edge cases and common mistakes
- Source equals destination. The search marks the source first, so
validPath(1, [], 0, 0)returnstrue: you are already there. - No edges. With
edges = []and two different vertices, nothing is reachable and the answer isfalse. - Isolated or disconnected vertices. A vertex with no edges has an empty neighbor list, and the search stops there. Parts of the graph that are not connected to the source are never visited.
- Forgetting the reverse edge. Storing only
edge[0]toedge[1]makes the graph directed. The first example would still pass, but a case likeedges = [[1, 0]]with source 0 and destination 1 would wrongly givefalse. - Marking after the recursive calls. If the mark came after the loop, cycles would be followed endlessly until the stack overflowed.
- Using
includeson the set. Sets have noincludesmethod. Calling it throws aTypeError.
Testing
n = 3,edges = [[0, 1], [1, 2], [2, 0]],source = 0,destination = 2givestrue.n = 6,edges = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]],source = 0,destination = 5givesfalse.n = 1,edges = [],source = 0,destination = 0givestrue.n = 2,edges = [[1, 0]],source = 0,destination = 1givestrue.