Find If Path Exists

Problem Statement

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.

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.

Try here before watching the video.

Video Explanation

Java Code

class Solution {

    public List<List<Integer>> buildGraph(int[][] edges, int n) {
        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]);
        }

        return graph;

    }

    private boolean solve(int node, int destination, List<List<Integer>> graph, boolean[] visited) {
        if(node == destination) return true;
        visited[node] = true;

        boolean reached = false;
        for(int nbr : graph.get(node)) {
            if(!visited[nbr]) {
                reached = reached || solve(nbr, destination, graph, visited);
                if(reached) return true;
            }
        }
        return reached;
    }

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = buildGraph(edges, n);
        boolean[] visited = new boolean[n];
        return solve(source, destination, graph, visited);
    }
}

C++ Code

class Solution {
public:
    vector<std::vector<int>> buildGraph(vector<vector<int>>& edges, int n) {
        vector<vector<int>> graph(n);
        
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        return graph;
    }

    bool solve(int node, int destination, const vector<vector<int>>& graph, vector<bool>& visited) {
        if (node == destination) return true;
        visited[node] = true;

        bool reached = false;
        for (int nbr : graph[node]) {
            if (!visited[nbr]) {
                reached = reached || solve(nbr, destination, graph, visited);
                if (reached) return true;
            }
        }
        return reached;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph = buildGraph(edges, n);
        vector<bool> visited(n, false);
        return solve(source, destination, graph, visited);
    }
};

class Solution:
    def buildGraph(self, edges: List[List[int]], n: int) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            
        return graph

    def solve(self, node: int, destination: int, graph: List[List[int]], visited: List[bool]) -> bool:
        if node == destination:
            return True
        visited[node] = True

        reached = False
        for nbr in graph[node]:
            if not visited[nbr]:
                reached = reached or self.solve(nbr, destination, graph, visited)
                if reached:
                    return True
        return reached

    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = self.buildGraph(edges, n)
        visited = [False] * n
        return self.solve(source, destination, graph, visited)

Javascript Code

var validPath = function(n, edges, source, destination) {
    const buildGraph = (edges, n) => {
        const graph = Array.from({length: n}, () => []);
        
        edges.forEach(edge => {
            graph[edge[0]].push(edge[1]);
            graph[edge[1]].push(edge[0]);
        });
        
        return graph;
    };

    const solve = (node, destination, graph, visited) => {
        if (node === destination) return true;
        visited[node] = true;

        let reached = false;
        for (const nbr of graph[node]) {
            if (!visited[nbr]) {
                reached = reached || solve(nbr, destination, graph, visited);
                if (reached) return true;
            }
        }
        return reached;
    };

    const graph = buildGraph(edges, n);
    const visited = new Array(n).fill(false);
    return solve(source, destination, graph, visited);
};

Go Code

func buildGraph(edges [][]int, n int) [][]int {
    graph := make([][]int, n)
    
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    
    return graph
}

func solve(node, destination int, graph [][]int, visited []bool) bool {
    if node == destination {
        return true
    }
    visited[node] = true

    reached := false
    for _, nbr := range graph[node] {
        if !visited[nbr] {
            reached = reached || solve(nbr, destination, graph, visited)
            if reached {
                return true
            }
        }
    }
    return reached
}

func validPath(n int, edges [][]int, source, destination int) bool {
    graph := buildGraph(edges, n)
    visited := make([]bool, n)
    return solve(source, destination, graph, visited)
}

Complexity Analysis

Time Complexity: O(V + E), where V is the total number of vertices and E is the number of edges.
Space Complexity: O(V + E), where V is the total number of vertices and E is the number of edges.