Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
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