Problem overview
The method validPath receives n, the number of vertices labeled 0 to n - 1, a list of edges, and two vertices, source and destination. Each edge [u, v] connects two vertices in both directions. The method returns true if you can walk from source to destination along edges, and false otherwise.
In the first example, n = 3 and edges = [[0,1],[1,2],[2,0]] form a triangle. From vertex 0 you can reach vertex 2 directly or through vertex 1, so the answer is true. In the second example, n = 6 with edges [[0,1],[0,2],[3,5],[5,4],[4,3]] has two separate groups, {0, 1, 2} and {3, 4, 5}. Vertex 0 can't reach vertex 5, so the answer is false.
Approach: explore everything reachable from the source
An edge list is awkward for walking: to find a vertex's neighbours you would scan every edge. So the first step is to build an adjacency list, where entry i holds the neighbours of vertex i.
Then run a depth-first search (DFS) from source. DFS goes as deep as it can along one neighbour before trying the next, and it records every vertex it reaches in a visited set. When the search ends, visited holds exactly the vertices connected to source, and the answer is whether destination is among them.
The visited set does two jobs. Marking a vertex before exploring its neighbours stops the search from walking around a cycle forever, as in the triangle above. And skipping visited vertices means each one is processed once, however many edges lead to it.
Step by step
- Build the adjacency list. Create
graphasnempty arrays withArray.from, so indexican hold vertexi's neighbours. - Create the
visitedset as aSet<number>, which answers "have we been here?" in constant time on average. - Loop over
edgeswithfor...of. Eachedgeis a pair:edge[0]andedge[1]are its endpoints. - Record each edge in both directions. The graph is bi-directional, so push each endpoint onto the other's list. With one direction only, the search would miss paths that run against the listed order.
- Start the search with
this.dfs(source, graph, visited). The method is in the same class, so it is called throughthis. - Return
visited.has(destination). ASetuseshas. - Write
dfs. It takes the currentnode, thegraphand thevisitedset, and returnsvoid. - Mark
nodeas visited first, before looking at its neighbours, so a neighbour that leads back sees it as already visited. - Loop over
graph[node]withadjacentNodeas the loop variable. - Recurse only on unvisited neighbours, passing the same
graphandvisited. Without that check, two neighbours would call each other forever.
The solution in TypeScript
class Solution {
validPath(n: number, edges: number[][], source: number, destination: number): boolean {
const graph: number[][] = Array.from({length: n}, () => []);
const visited: Set<number> = 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: number, graph: number[][], visited: Set<number>): void {
visited.add(node);
for (const adjacentNode of graph[node]) {
if (!visited.has(adjacentNode)) {
this.dfs(adjacentNode, graph, visited);
}
}
}
}
TypeScript and JavaScript details:
- Building the list with
Array.from.Array.from({length: n}, () => [])calls the function once per index, so every slot gets its own new empty array. The temptingnew Array(n).fill([])puts the same array in every slot: pushing tograph[0]would then show up ingraph[1]and all the rest. For example,new Array(3).fill([])followed by a singlepush(1)on the first slot gives[[1],[1],[1]]. - Annotations are erased.
number[][]andSet<number>help the compiler catch mistakes such as pushing a string, but they leave no trace in the compiled JavaScript. - Arrays and sets are passed by reference. Every recursive call receives the same
graphand the samevisited, so what one call adds is visible to all the others. That is whydfscan returnvoidand still deliver its result. Setmethods. The membership test ishas, notincludes(which arrays have). Usingincludeson a set is a compile error.- Methods need
this. Writing plaindfs(...)inside the class is a reference to a variable that doesn't exist; the call isthis.dfs(...).
Complexity
Let V be the number of vertices and E the number of edges.
Time: O(V + E). Building the adjacency list takes O(V + E). The search visits each vertex once and looks at each edge from both ends, which is 2E checks in total.
Space: O(V + E). The adjacency list stores 2E entries across V arrays, and the set holds up to V vertices. The recursion adds a call stack as deep as the longest chain of unvisited vertices the search follows.
That call stack has a limit. The statement allows up to 200,000 vertices, and in a test run, a graph shaped as a single path of 50,000 vertices made this solution throw RangeError: Maximum call stack size exceeded. The depth at which that happens varies, so it is a caution for very deep graphs rather than an exact number. A loop with an explicit stack (an array that you push to and pop from) avoids the limit.
Edge cases and common mistakes
- Source equals destination.
validPath(1, [], 0, 0)istrue: the search marks the source before anything else, and the source is the destination. - No edges and different vertices.
validPath(2, [], 0, 1)isfalse. - Direction of the listed edge. With
edges = [[0,1]], asking for a path from 1 to 0 returnstrue, because both directions are recorded. - Forgetting the second
push. The search would only follow edges in the listed direction and miss valid paths. - Marking a vertex only after recursing into its neighbours. On a cycle, the calls would never stop.
- Disconnected groups. The second example shows it: the search from 0 never touches 3, 4 or 5, so they stay out of
visited.
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 = [],source = 0,destination = 1givesfalse.n = 2,edges = [[0,1]],source = 1,destination = 0givestrue.