Space
Open
From Fieldwork
Scales
Archive
Python has a default recursion limit (usually 1000) that will cause a RecursionError on the large constraints of this problem (N=200,000) unless you manually increase the limit. Therefore, the iterative BFS is the standard, production-ready solution.
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# Edge case: If start and end are the same, we are already there
if source == destination:
return True
# 1. Build Adjacency List
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# 2. Initialize BFS
visited = set([source])
queue = deque([source])
# 3. Process Queue
while queue:
current_node = queue.popleft()
# Optional: Check here (or before adding to queue)
if current_node == destination:
return True
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return FalseUnion find is extremely fast and handles the logic without explicitly building the graph structure (adjacency list).
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if source == destination:
return True
root = list(range(n))
rank = [1] * n
def find(x):
if root[x] != x:
root[x] = find(root[x]) # Path compression
return root[x]
def union(x, y):
rootX, rootY = find(x), find(y)
if rootX != rootY:
# Union by rank optimization
if rank[rootX] > rank[rootY]:
root[rootY] = rootX
elif rank[rootX] < rank[rootY]:
root[rootX] = rootY
else:
root[rootY] = rootX
rank[rootX] += 1
for u, v in edges:
union(u, v)
return find(source) == find(destination)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode