Find if Path Exists in Graph

LeetCode 2121 | Difficulty: Easy

Easy

Problem Description

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] = [u~i~, v~i~] denotes a bi-directional edge between vertex u~i~ and vertex v~i~. 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**.

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
- 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.

Constraints:

- `1 <= n <= 2 * 10^5`

- `0 <= edges.length <= 2 * 10^5`

- `edges[i].length == 2`

- `0 <= u~i~, v~i~ <= n - 1`

- `u~i~ != v~i~`

- `0 <= source, destination <= n - 1`

- There are no duplicate edges.

- There are no self edges.

Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

---

Solutions

Solution 1: C# (Best: 596 ms)

Metric	Value
Runtime	596 ms
Memory	80.3 MB
Date	2022-01-19

Solution

public class Solution {
    public bool ValidPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;

    Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    foreach (var edge in edges)
    {
        if (graph.ContainsKey(edge[0]))
            graph[edge[0]].Add(edge[1]);
        else graph.Add(edge[0], new List<int>() { edge[1] });

        if (graph.ContainsKey(edge[1]))
            graph[edge[1]].Add(edge[0]);
        else graph.Add(edge[1], new List<int>() { edge[0] });}

        Stack<int> q = new Stack<int>();
        List<int> visited = new List<int>();
        q.Push(source);
        visited.Add(source);
        while (q.Count != 0)
        {
            
            var front = q.Pop();
            if (!graph.ContainsKey(front)) continue;
            List<int> neighbors = graph[front];
            foreach (int neighbor in neighbors)
            {
                if (visited.Contains(neighbor)) continue;
                if (neighbor == destination) return true;
                q.Push(neighbor);
                visited.Add(neighbor);
            }
        }
    
    return false;
    }
}

📜 2 more C# submission(s)

Submission (2022-01-19) — 1073 ms, 79.5 MB

public class Solution {
    public bool ValidPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;

    Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    foreach (var edge in edges)
    {
        if (graph.ContainsKey(edge[0]))
            graph[edge[0]].Add(edge[1]);
        else graph.Add(edge[0], new List<int>() { edge[1] });

        if (graph.ContainsKey(edge[1]))
            graph[edge[1]].Add(edge[0]);
        else graph.Add(edge[1], new List<int>() { edge[0] });}

        Queue<int> q = new Queue<int>();
        List<int> visited = new List<int>();
        q.Enqueue(source);
        visited.Add(source);
        while (q.Count != 0)
        {
            
            var front = q.Dequeue();
            if (!graph.ContainsKey(front)) continue;
            List<int> neighbors = graph[front];
            foreach (int neighbor in neighbors)
            {
                if (visited.Contains(neighbor)) continue;
                if (neighbor == destination) return true;
                q.Enqueue(neighbor);
                visited.Add(neighbor);
            }
        }
    
    return false;
    }
}

Submission (2022-01-19) — 1936 ms, 88.7 MB

public class Solution {
    public bool ValidPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;

    Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    foreach (var edge in edges)
    {
        if (graph.ContainsKey(edge[0]))
            graph[edge[0]].Add(edge[1]);
        else graph.Add(edge[0], new List<int>() { edge[1] });

        if (graph.ContainsKey(edge[1]))
            graph[edge[1]].Add(edge[0]);
        else graph.Add(edge[1], new List<int>() { edge[0] });

        Stack<int> q = new Stack<int>();
        List<int> visited = new List<int>();
        q.Push(source);
        visited.Add(source);
        while (q.Count != 0)
        {
            
            var front = q.Pop();
            if (!graph.ContainsKey(front)) continue;
            List<int> neighbors = graph[front];
            foreach (int neighbor in neighbors)
            {
                if (visited.Contains(neighbor)) continue;
                if (neighbor == destination) return true;
                q.Push(neighbor);
                visited.Add(neighbor);
            }
        }
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.