Grokking Graph Algorithms for Coding Interviews

0% completed

​

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

You are also given starting node start, and a destination node end, return true if a path exists between the starting node and the destination node. Otherwise, return false.

Examples

Example 1:

  • Input: n = 4, edges = [[0,1],[1,2],[2,3]], start = 0, end = 3
  • Expected Output: true

.....

.....

.....

Like the course? Get enrolled and start learning!
Elena Feoktistova

Elena Feoktistova

· 2 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 1 reply
Manuel

Manuel

· a year ago

You never explained the list of edges representation, nor DFS with recursion. Problem 1 uses things not covered in the material I'm disappointed.

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 1 reply
K

kowusu01

· 3 months ago

I paid money for this course, am learning outside the course with AI. There is absolutely no intuition about why, just how. You are forced to memorize, and am not that type of student.