Problem overview
The method validPath receives n, the number of vertices labeled 0 to n - 1, and edges, an Array[Array[Int]] where each pair [u, v] is a two-way connection. It also receives a source and a destination. It returns true when you can walk from source to destination along edges.
In the first example, n = 3 and the edges form a triangle, so vertex 0 reaches vertex 2 directly or through vertex 1: the answer is true. In the second, n = 6: vertices 0, 1, 2 form one group and vertices 3, 4, 5 form another, with no edge between the groups, so 0 can't reach 5 and the answer is false.
Approach: explore everything reachable from the source
A path exists exactly when the destination is among the vertices reachable from the source. So the method explores the graph from the source and records every vertex it touches, then checks whether the destination is in that record.
Edges are given as a flat list, which is awkward for exploring. The first job is to build an adjacency list: an array where slot i holds the neighbors of vertex i. Because the graph is bi-directional, each edge [u, v] adds v to u's neighbors and u to v's neighbors.
The exploration is a depth-first search (DFS). Visit a vertex, mark it, then visit each unmarked neighbor in turn, going as deep as possible before coming back. Marking the vertex before looking at its neighbors is what stops the search from going around a cycle forever.
On the first example the adjacency list is 0: [1, 2], 1: [0, 2], 2: [1, 0]. The search marks 0, goes to 1, marks it, and from 1 reaches 2 and marks it. Back at 0, the neighbor 2 is already marked. The marked set is {0, 1, 2}, which contains the destination.
Step by step
- Create the adjacency list with
Array.fill(n)(mutable.ArrayBuffer[Int]()): an array ofnempty buffers, one per vertex.Array.fillevaluates its second argument once per slot, so every vertex gets its own buffer. - Create the visited set, an empty
mutable.Set[Int], to remember which vertices the search has reached. - Loop over
edges, naming each pairedge. - Record the edge both ways. Append
edge(1)to the buffer ofedge(0)andedge(0)to the buffer ofedge(1)with+=. With only one direction, the search would miss paths that walk an edge backward. - Run the search by calling
dfs(source, graph, visited). Afterwardsvisitedholds every vertex reachable from the source. - Return
visited.contains(destination)as the last expression. - Declare
dfswith the parametersnode,graphandvisited, returningUnit. The set is shared by reference, so changes made by recursive calls are visible to the caller. - Mark
nodeas visited first, before any recursion. - Loop over the neighbors in
graph(node), naming each oneadjacentNode. - Recurse only on unvisited neighbors. Without the check, two neighbors would call each other forever.
The solution in Scala
class Solution {
def validPath(n: Int, edges: Array[Array[Int]], source: Int, destination: Int): Boolean = {
val graph = Array.fill(n)(mutable.ArrayBuffer[Int]())
val visited = mutable.Set[Int]()
for (edge <- edges) {
graph(edge(0)) += edge(1)
graph(edge(1)) += edge(0)
}
dfs(source, graph, visited)
visited.contains(destination)
}
def dfs(node: Int, graph: Array[mutable.ArrayBuffer[Int]], visited: mutable.Set[Int]): Unit = {
visited.add(node)
for (adjacentNode <- graph(node)) {
if (!visited.contains(adjacentNode)) {
dfs(adjacentNode, graph, visited)
}
}
}
}
The Scala details worth a closer look:
- The
mutableprefix. The code writesmutable.ArrayBufferandmutable.Set, so it relies onimport scala.collection.mutable. In a standalone file, put that import at the top. Scala's plainSetandListare immutable. Array.fill(n)(...)and sharing. The element expression runs again for every slot. Passing one existing buffer instead, as inval b = mutable.ArrayBuffer[Int](); val bad = Array.fill(3)(b), puts the same buffer in all three slots: afterbad(0) += 7all three slots print asList(7). With the form used here, only slot 0 changes.- Mutable
Set.visited.add(node)changes the set in place and returns aBooleansaying whether the element was new. The solution ignores that value. - Methods in the same class call each other by name, so
validPathcan calldfs, which is defined after it. - Loops over a buffer.
for (adjacentNode <- graph(node))iterates over that vertex's neighbors. Scala indexes arrays with parentheses.
Complexity
Let m be the number of edges.
Time: O(n + m). Building the adjacency list takes O(n + m). The search marks each vertex once and looks at each edge from both of its ends.
Space: O(n + m). The adjacency list holds 2m entries and n buffers. The visited set holds up to n vertices. The recursion also uses stack space, up to one frame per vertex on a long chain.
Edge cases and common mistakes
- Source equals destination. The source is marked first, so a call with
n = 1, no edges and both vertices equal to 0 returnstrue. - No edges and different vertices. Only the source gets marked, so the answer is
false. - Edge order inside a pair.
[1, 0]connects the two vertices in both directions, so searches from 0 and from 1 both succeed. - Adding each edge in one direction only. A graph that should be two-way would then answer
falsewhenever the path walks an edge against its listed direction. - Marking after recursing. If you mark a vertex only after its neighbors are done, a cycle sends the search around it forever until the stack overflows.
- Very long paths. Recursion depth equals the length of the path being followed. For a chain of 200,000 vertices, which is within the stated limits, this recursive version can overflow the stack with the JVM's default stack size. An explicit stack, a queue (BFS) or a union-find avoids that limit.
Testing
n = 3,edges = [[0,1],[1,2],[2,0]], source 0, destination 2 givestrue.n = 6,edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5 givesfalse.n = 1,edges = [], source 0, destination 0 givestrue.n = 3,edges = [[0,1]], source 0, destination 2 givesfalse.
