What is the brute force approach and complexity for Find if Path Exists in Graph?

Keep marking new nodes by scanning every edge again and again until nothing changes with time complexity O(V · E) and space complexity O(V).

What is the optimal approach and complexity for Find if Path Exists in Graph?

Build a neighbour list once, then one BFS from the source; the answer is whether the destination was visited with optimal time complexity O(V + E) and space complexity O(V + E).

How do you identify the pattern for Find if Path Exists in Graph?

Look for key signals in the prompt: "Can you get from A to B" indicates A yes-or-no question about connection, not a shortest path. A plain reachability search is enough.; "edges work in both directions" indicates Each edge goes into the neighbour list of both ends. Forgetting one side breaks the search.; "nodes labelled 0 to n − 1" indicates The visited marks can be a plain array indexed by the node label..

Find if Path Exists in Graph

Easy·LeetCode #1971Basic Anchor

LeetCode

Jump:

30-Second Mental ModelGraph BFS / DFS: Connectivity (reachability from one source)

Complexity:O(V · E)→O(V + E)

Key Insight

Build an adjacency list: for each edge [u, v], put v in the list of u and u in the list of v. Then run BFS from source, marking each node when it is pushed. A node is marked exactly when it can be reached, so the answer is the mark on destination.

Core Validity Invariant

A node counts as reached only when a walk from source to it exists, so a node gets marked only when it is one edge away from a node that is already reached.

Problem

You are given n nodes numbered 0 to n − 1, and a list of edges. Each edge [u, v] joins node u and node v, and it works in both directions.

You are also given a source node and a destination node. Return true if you can walk from source to destination along the edges, and false if you cannot.

Input

An integer n, a list edges where each entry is a pair [u, v], and two node numbers source and destination.

Output

true if a walk from source to destination exists, otherwise false.

Example 1

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

Output: true

There are two ways to get from 0 to 2: the direct edge 2–0, or the walk 0 → 1 → 2.

Example 2

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

Output: false

Nodes 0, 1 and 2 form one group, and nodes 3, 4 and 5 form another. No edge joins the two groups, so 5 cannot be reached from 0.

Constraints

• 1 ≤ n ≤ 2 · 10^5
• 0 ≤ edges.length ≤ 2 · 10^5
• edges[i].length = 2, with 0 ≤ u, v ≤ n − 1 and u ≠ v
• There are no duplicate edges.
• 0 ≤ source, destination ≤ n − 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I stand on source, which nodes can I step to right away? Which nodes can I reach from those?
2.
An edge [u, v] works both ways. What should I store for each node so I can find its neighbours quickly?
3.
Does the question ask for the shortest walk, or only whether a walk exists?
4.
If I keep a record of the nodes I have already reached, how do I stop myself from walking in circles?
5.
When I have explored everything reachable from the source, what does that set look like if the destination is not in it?

Brute force approach

Idea

Start with only source marked as reached. Scan the whole edge list: if one end of an edge is reached, mark the other end too. Repeat the scan until one full pass marks nothing new. Then check whether destination is marked.

Thinking process

1
The question asks whether a walk exists, so I only need the set of nodes I can reach from the source. I do not need the walk itself.
2
On the dry run [[3,4],[2,3],[1,2],[0,1],[0,5]] with source 0, only node 0 is marked at the start.
3
Pass 1 reaches 1 and 5. The edge [1,2] comes before [0,1] in the list, so node 2 is still missing when [1,2] is read.
4
Pass 2 reaches 2, pass 3 reaches 3, and pass 4 reaches 4. Pass 5 marks nothing new, so we stop. Node 4 is marked, so the answer is true.
5
Each pass reads all 5 edges. In the worst case one new node appears per pass, so the passes add up.

Visual

Blue = the edge being read now, green = reached, purple = reached in this step. The edges are listed backwards, so each pass reaches only a little more.

Repeat passes until nothing changesn = 6, edges = [[3,4],[2,3],[1,2],[0,1],[0,5]], source = 0, destination = 4step 1/27

graph

reached

State

pass: 0
reached: 1

Start: only node 0 is reached

Node 0 is the source, so it is reached. The other nodes stay unmarked until an edge brings them in.

Code & Implementation

brute.cpp

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // reached[i] = true when we already know a walk from source to i.
        vector<bool> reached(n, false);
        reached[source] = true;

        bool changed = true;
        while (changed) {                        // repeat passes until one pass adds nothing
            changed = false;
            for (auto& e : edges) {              // read every edge, in the order given
                int a = e[0], b = e[1];
                // Edges work both ways: if one end is reached, the other end is too.
                if (reached[a] && !reached[b]) { reached[b] = true; changed = true; }
                if (reached[b] && !reached[a]) { reached[a] = true; changed = true; }
            }
        }
        return reached[destination];
    }
};

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // reached[i] = true when we already know a walk from source to i.
        boolean[] reached = new boolean[n];
        reached[source] = true;

        boolean changed = true;
        while (changed) { // repeat passes until one pass adds nothing
            changed = false;
            for (int[] e : edges) { // read every edge, in the order given
                int a = e[0], b = e[1];
                // Edges work both ways: if one end is reached, the other end is too.
                if (reached[a] && !reached[b]) { reached[b] = true; changed = true; }
                if (reached[b] && !reached[a]) { reached[a] = true; changed = true; }
            }
        }
        return reached[destination];
    }
}

from typing import List

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # reached[i] = true when we already know a walk from source to i.
        reached = [False] * n
        reached[source] = True

        changed = True
        while changed:  # repeat passes until one pass adds nothing
            changed = False
            for e in edges:  # read every edge, in the order given
                a, b = e[0], e[1]
                # Edges work both ways: if one end is reached, the other end is too.
                if reached[a] and not reached[b]:
                    reached[b] = True
                    changed = True
                if reached[b] and not reached[a]:
                    reached[a] = True
                    changed = True

        return reached[destination]

export function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    // reached[i] = true when we already know a walk from source to i.
    const reached: boolean[] = Array(n).fill(false);
    reached[source] = true;

    let changed = true;
    while (changed) { // repeat passes until one pass adds nothing
        changed = false;
        for (const e of edges) { // read every edge, in the order given
            const a = e[0], b = e[1];
            // Edges work both ways: if one end is reached, the other end is too.
            if (reached[a] && !reached[b]) { reached[b] = true; changed = true; }
            if (reached[b] && !reached[a]) { reached[a] = true; changed = true; }
        }
    }
    return reached[destination];
}

Complexity

Time O(V · E)Space O(V)

V is the number of nodes (n) and E is the number of edges. Each pass reads all E edges. A pass that changes anything marks at least one of the V nodes, so there are at most V changing passes plus one final check. The dry run needs 5 passes for 5 edges.

Optimized approach

Idea

Start from brute force

The brute force scans the whole edge list on every pass to find which nodes are next to the reached set. Each pass often adds only one node.

Find the repeated work

On the dry run, pass 2 reads all five edges again just to add node 2. Almost every edge is read again on every pass, even the ones that can never add anything new.

Define the state — what variables do I need?

adj: adj[u] lists every node one edge away from u. Every edge is stored in both directions.
visited: visited[u] is true once u has been pushed into the queue, which means it is reached.
queue: Reached nodes whose neighbours have not been checked yet.

Define validity

A node counts as reached only when a walk from source to it exists, so a node gets marked only when it is one edge away from a node that is already reached.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Build adj from every edge, in both directions. Push source and mark it.

Every later step needs the neighbours of some node, so the lists come first. Marking source first means the walk starts from a reached node.

Pop u from the queue

For each neighbour v of u: if v is not visited, mark it and push it.

If u is reached and v is one edge from u, then v is reached too. Marking when pushed stops v from being pushed again from another neighbour.

What does the current window add to the answer?

Each pop reaches the neighbours of one node. When the queue is empty, visited holds every reachable node, so visited[destination] is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // Neighbour lists. Every edge goes in both directions.
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }

        // BFS from source. A node is marked when it is pushed, so it enters the queue once.
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(source);
        visited[source] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return visited[destination];
    }
};

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // Neighbour lists. Every edge goes in both directions.
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        // BFS from source. A node is marked when it is pushed, so it enters the queue once.
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(source);
        visited[source] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                }
            }
        }
        return visited[destination];
    }
}

from typing import List
from collections import deque

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # Neighbour lists. Every edge goes in both directions.
        adj: List[List[int]] = [[] for _ in range(n)]
        for e in edges:
            adj[e[0]].append(e[1])
            adj[e[1]].append(e[0])

        # BFS from source. A node is marked when it is pushed, so it enters the queue once.
        visited = [False] * n
        q = deque([source])
        visited[source] = True
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)

        return visited[destination]

export function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    // Neighbour lists. Every edge goes in both directions.
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const e of edges) {
        adj[e[0]].push(e[1]);
        adj[e[1]].push(e[0]);
    }

    // BFS from source. A node is marked when it is pushed, so it enters the queue once.
    const visited: boolean[] = Array(n).fill(false);
    const q: number[] = [source];
    visited[source] = true;
    let head = 0;

    while (head < q.length) {
        const u = q[head++];
        for (const v of adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    return visited[destination];
}

Complexity

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

The adjacency list stores each edge twice, so it takes O(V + E) space. BFS pushes each node once and reads each stored neighbour once. Another way to answer this is Union-Find: union the two ends of every edge, then check whether source and destination have the same root. It also runs in about O(V + E), but BFS and DFS are the tools the rest of this sub-pattern uses.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Keep marking new nodes by scanning every edge again and again until nothing changes	O(V · E)	O(V)
Optimal	Build a neighbour list once, then one BFS from the source; the answer is whether the destination was visited	O(V + E)	O(V + E)

Why does this belong to this pattern?

Clues in the problem statement

“Can you get from A to B”A yes-or-no question about connection, not a shortest path. A plain reachability search is enough.
“edges work in both directions”Each edge goes into the neighbour list of both ends. Forgetting one side breaks the search.
“nodes labelled 0 to n − 1”The visited marks can be a plain array indexed by the node label.

Graph with n nodes and two-way edges+adjacency list+visited marks+BFS (or DFS) from source→Graph BFS / DFS: Connectivity (reachability from one source)

The question asks whether one node can reach another, so the search only needs a yes or no. The move is the same in every connectivity problem: build an adjacency list once, then run one traversal from the source, which marks everything in its group. This is the anchor of the sub-pattern, because the edges are two-way and there is only one source. The next questions change the input: Keys and Rooms makes the edges one-way, and Number of Provinces asks how many groups there are.

Don't make this mistake

Adding each edge in one direction only

✗ adj[u].push_back(v);

✓ adj[u].push_back(v); adj[v].push_back(u);

Take the edges [[1,0],[1,2]] with source 0 and destination 2. The answer is true (0 → 1 → 2). With only one direction, only adj[1] gets entries and list 0 stays empty. BFS from 0 finds nothing, so the code returns false.

Checking only the source's direct neighbours

✗ return find(adj[source].begin(), adj[source].end(), destination) != adj[source].end();

✓ BFS or DFS from source, then return visited[destination];

Being one edge away is not the same as being reachable. On the dry run, adj[0] = [1, 5] does not contain 4, so this code returns false. The walk 0 → 1 → 2 → 3 → 4 has four edges, so the answer is true.

No visited marks

✗ queue<int> q; q.push(source); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) q.push(v); }

✓ if (!visited[v]) { visited[v] = true; q.push(v); }

Nothing stops a node from being pushed again. On the dry run, node 0 pushes 1, node 1 pushes 0 back, and 0 pushes 1 again. The queue never empties.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Keys and Rooms