Skip to main content

1971. Find if Path Exists in Graph

easy

Given an undirected graph with n nodes and an edge list, decide whether there's a path from source to destination. The simplest possible reachability question — DFS, BFS, or union-find all work.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Constraints

  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= source, destination <= n - 1
  • There are no duplicate edges.
  • There are no self edges.

Examples

Example 1

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

Explanation: There are two paths from vertex 0 to vertex 2: 0 -> 1 -> 2 and 0 -> 2.

Example 2

Input
n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output
false

Explanation: There is no path from vertex 0 to vertex 5.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Build an adjacency list from edges. Then ask: starting from source, can you reach destination by following edges?

Hint 2

Either BFS or DFS from source, tracking visited nodes so you don't loop forever on cycles. Return true the moment you pop destination.

Hint 3

Union-find is also natural here: union both endpoints of every edge, then test whether source and destination share the same root.

Solution approach

Reveal approach

Build an adjacency list, then BFS from source: push source into a queue, mark visited, and pop-and-expand neighbors until either destination shows up (return true) or the queue empties (return false). DFS is symmetric — same complexity, just recursion or an explicit stack. Union-find is the third option and is particularly clean for batched queries: iterate edges and union(u, v); afterwards find(source) == find(destination) answers the question in near-constant time. All three are O(V + E) time and O(V + E) space. Pick BFS for level-order intuition, DFS for code brevity, union-find when you'll repeat the query.

Complexity

Time
O(V + E)
Space
O(V + E)

Related patterns

  • graph-bfs
  • graph-dfs
  • union-find

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Find if Path Exists in Graph and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →