LeetCode 1971: Find if Path Exists in Graph Solution

Master LeetCode problem 1971 (Find if Path Exists in Graph), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1971. Find if Path Exists in Graph

Easy

Depth-First Search Breadth-First Search Union Find Graph

Problem Explanation

Explanation:

To solve this problem, we can perform a graph traversal starting from the source vertex and check if we can reach the destination vertex. We can use either Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph.

Algorithmic Steps:

Create an adjacency list to represent the graph based on the given edges.
Initialize a data structure to keep track of visited vertices.
Start a DFS or BFS from the source vertex and traverse the graph while updating the visited set.
If the destination vertex is found during the traversal, return true. Otherwise, return false.

Time Complexity:

The time complexity of this approach is O(N + E), where N is the number of vertices and E is the number of edges.

Space Complexity:

The space complexity of this approach is O(N + E) for storing the adjacency list and visited set.

: :

Solution Code

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        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]);
        }
        Set<Integer> visited = new HashSet<>();
        return dfs(graph, source, destination, visited);
    }
    
    private boolean dfs(List<List<Integer>> graph, int source, int destination, Set<Integer> visited) {
        if (visited.contains(source)) {
            return false;
        }
        if (source == destination) {
            return true;
        }
        visited.add(source);
        for (int neighbor : graph.get(source)) {
            if (dfs(graph, neighbor, destination, visited)) {
                return true;
            }
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1971 (Find if Path Exists in Graph)?

This page provides optimized solutions for LeetCode problem 1971 (Find if Path Exists in Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1971 (Find if Path Exists in Graph)?

The time complexity for LeetCode 1971 (Find if Path Exists in Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1971 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1971 in Java, C++, or Python.

Back to LeetCode Solutions