Grokking Graph Algorithms for Coding Interviews
Vote

0% completed

​

Problem 1: Find if Path Exists in Graph(easy)

Problem Statement

Given an undirected graph, represented as a list of edges. Each edge is illustrated as a pair of integers [u, v], signifying that there's a mutual connection between node u and node v.

This input format is an edge list, which is covered in the Graph Representations lesson. An edge list is compact to write down but slow to search, so the usual first step is to turn it into an adjacency list in one pass, and then run a traversal over that.

You are also given starting node `start

.....

.....

.....

Like the course? Get enrolled and start learning!
Massi Faqiri

Massi Faqiri

· 6 days ago

With n up to 200,000, recursion implementation of DFS can lead to overflow. I think this solution would be better off with BFS or stack-based DFS.

Raul Acosta

Raul Acosta

· 2 years ago

The solution returns true at n = 1, but there can be no self-edges. This should return false.

Show 2 replies
Elena Feoktistova

Elena Feoktistova

· 3 years ago

import java.util.*;

public class Solution {
    private boolean[] visited; // To keep track of visited nodes

    public boolean validPath(int n, int[][] edges, int start, int end) {
        if (edges.length == 0) return false;
        visited = new boolean[n];
        visited[edges[0][0]] = true;
        for (int i = 0; i < edges.length; i++) {
            if (visited[edges[i][0]] == true) {
                visited[edges[i][1]] = true;
            }
        }

        return visited[start] == true && visited[end] == true;
    }

}
Show 2 replies

Reading Progress

0%

Vote for new content