algoadvance

Leetcode 1971. Find if Path Exists in Graph

Problem Statement

You are given an undirected graph of n nodes labeled from 0 to n - 1 and an integer n representing the number of nodes. You are also given a 2D array edges, where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i. Given two integers source and destination, return true if there is a valid path from source to destination, or false otherwise.

Clarifying Questions

  1. Graph Characteristics: Are there any self-loops or parallel edges allowed?
    • Typically, no self-loops or parallel edges are allowed unless explicitly mentioned.
  2. Input Constraints:
    • Number of nodes, n, 1 <= n <= 200000.
    • The number of edges, edges.length, 0 <= edges.length <= 200000.
    • Node labels edges[i][0] and edges[i][1] will fall within [0, n-1].
  3. Special Cases:
    • If source is the same as destination, should we return true? Yes.
    • What should be returned if there are no edges in the graph and source is not equal to destination? false.

Strategy

  1. Graph Representation: Use an adjacency list to represent the graph.
  2. Traversal Technique: Utilize Breadth-First Search (BFS) for traversal because it helps in finding the shortest path in terms of edges, but Depth-First Search (DFS) is also suitable for this problem.
  3. Visited Set: Maintain a set of visited nodes to avoid cycles and redundant checks.

Code

Here’s the Java code to solve the problem:

import java.util.*;

public class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }
        
        // Create an adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // Implement BFS
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(source);
        visited.add(source);
        
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            
            for (int neighbor : graph.get(currentNode)) {
                if (neighbor == destination) {
                    return true;
                }
                
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return false;
    }
}

Time Complexity

  1. Graph Construction: O(V + E) where V is the number of vertices (n) and E is the number of edges.
  2. Graph Traversal: O(V + E) since each node and edge is processed once in BFS.

Overall, the time complexity is O(V + E), making this approach efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI