How do you solve Find if Path Exists in Graph?

Build an adjacency list representation of the graph for O(1) neighbor access. Use a recursive DFS starting from the source node, marking visited nodes to avoid cycles. If the destination node is encountered during traversal, return true immediately. If DFS completes without finding the destination, return false. This guarantees O(n + m) time complexity, where n is the number of nodes and m is the number of edges.

What pattern does Find if Path Exists in Graph use?

The Pattern: DFS (Graph Connectivity) The Heuristic: When checking if a path exists between two nodes in an unweighted graph, use DFS to explore reachable nodes from the source, marking visited nodes to avoid cycles, and terminate early upon reaching the destination.

Find if Path Exists in Graph — DFS

Q: What is the time complexity of Find if Path Exists in Graph?

O(n + m). Each node is visited at most once, and each edge is explored at most twice (once from each endpoint) during the DFS traversal, resulting in linear time relative to the graph size.

Problem

Given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges, determine if there is a valid path from the source node to the destination node.

1 ≤ n ≤ 2 * 10⁵
0 ≤ edges.length ≤ 2 * 10⁵
edges[i].length == 2
0 ≤ ui, vi < n
ui != vi
0 ≤ source, destination < n
There are no duplicate edges.

Example

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output: true

The edges create a connected cycle among nodes {0,1,2}, so every node is reachable from every other node. Starting from 0, a DFS (or BFS) marks reachable nodes by following edges while avoiding revisits via a visited set. Node 2 is reachable from 0 (either directly via edge (2,0) or through 0 → 1 → 2), so the search will eventually visit 2 and return true.

Approach

Straightforward Solution

A brute-force approach might attempt to enumerate all possible paths between source and destination, which is exponential and infeasible for large graphs.

Core Observation

The problem reduces to checking connectivity between two nodes in an undirected graph. This is a classic graph traversal problem where the existence of a path corresponds to reachability in the graph.

Path to Optimal

Preview

Recognizing that the problem is about reachability, a Depth-First Search (DFS) or Breadth-First Search (BFS) can efficiently explore the graph starting from the source node…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list representation of the graph for O(1) neighbor access. Use a recursive DFS starting from the source node, marking visited nodes to avoid cycles…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Each node is visited at most once, and each edge is explored at most twice (once from each endpoint) during the DFS traversal, resulting in linear time relative to the graph size.

Space

O(n + m)

The adjacency list requires O(n + m) space to store all edges, and the visited set requires O(n) space to track visited nodes. The recursion stack can go as deep as O(n) in the worst case.

Solution

Python

1from collections import defaultdict
2
3class Solution:
  def validPath(self, n: int, edges: [[int]], source: int, destination: int) -> bool:
      graph = defaultdict(list)
      
      for u, v in edges:
          graph[u].append(v)
          graph[v].append(u) 
      
      visited = set()
12
      def dfs(node):
          if node == destination:  
              return True
          visited.add(node)
          
          for neighbor in graph[node]:
              if neighbor not in visited and dfs(neighbor):
                  return True
          return False 
22
      return dfs(source)

Step-by-Step Solution

1

Construct Adjacency List to Represent the Undirected Graph

5graph = defaultdict(list)
7for u, v in edges:
8    graph[u].append(v)
9    graph[v].append(u) 

Objective

To build a graph representation that allows efficient neighbor lookups for each node.

Key Insight

An adjacency list is the most efficient way to represent sparse graphs, enabling O(1) average-time access to neighbors. Since the graph is undirected, each edge is added to both nodes' adjacency lists, ensuring bidirectional traversal during DFS.

Interview Quick-Check

Core Logic

Building the adjacency list from edges allows the DFS to quickly access all neighbors of a node without scanning the entire edge list.

Common Pitfalls & Bugs

Forgetting to add both directions for undirected edges leads to incomplete graph representation and incorrect traversal.

2

Track Visited Nodes to Avoid Revisiting and Cycles

To maintain a record of nodes already explored to prevent infinite recursion and redundant work.

3

Recursively Explore Nodes Using DFS and Terminate Early on Destination

To traverse the graph depth-first from the source, returning true immediately upon reaching the destination.

4

Initiate DFS from Source and Return Final Reachability Result

To start the DFS traversal from the source node and return whether a path to the destination exists.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 14 Critical

if node == destination:

Check if the current node is the destination.

This line is the critical early-exit condition that allows the DFS to stop searching as soon as the destination is reached, preventing unnecessary exploration and ensuring efficiency.

Line 11 Critical

visited = set()

Create a set to track visited nodes.

The visited set prevents revisiting nodes, which is critical to avoid infinite loops in cyclic graphs and to ensure linear time complexity.

Line 16 Critical

visited.add(node)

Mark the current node as visited.

Adding the node to visited before exploring neighbors prevents revisiting it in future recursive calls, avoiding cycles and redundant work.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does marking nodes as visited during DFS prevent infinite loops and ensure correctness?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find if Path Exists in Graph from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find if Path Exists in Graph drill

or drill a free problem

1	`from collections import defaultdict`
2
3	`class Solution:`
4	`def validPath(self, n: int, edges: [[int]], source: int, destination: int) -> bool:`
5	`graph = defaultdict(list)`
6
7	`for u, v in edges:`
8	`graph[u].append(v)`
9	`graph[v].append(u)`
10
11	`visited = set()`
12
13	`def dfs(node):`
14	`if node == destination:`
15	`return True`
16	`visited.add(node)`
17
18	`for neighbor in graph[node]:`
19	`if neighbor not in visited and dfs(neighbor):`
20	`return True`
21	`return False`
22
23	`return dfs(source)`

5	`graph = defaultdict(list)`
7	`for u, v in edges:`
8	`graph[u].append(v)`
9	`graph[v].append(u)`