Approach: Union-Find

union every edge, then check whether 0 and n-1 share a root

Complexity: O(n + e) time, O(n) space.

Full Solution — all languages

class Solution:
    def validPath(self, n, edges):
        par = list(range(n))
        def find(x):
            while par[x] != x:
                par[x] = par[par[x]]; x = par[x]
            return x
        for a, b in edges:
            par[find(a)] = find(b)
        return find(0) == find(n - 1)

import java.util.*;
class Solution {
    public boolean validPath(int n, int[][] edges) {
        int[] par = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        for (int[] e : edges) par[find(par, e[0])] = find(par, e[1]);
        return find(par, 0) == find(par, n - 1);
    }
    int find(int[] par, int x) {
        while (par[x] != x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: bool validPath(int n, vector<vector<int>>& edges) {
        vector<int> par(n);
        for (int i = 0; i < n; i++) par[i] = i;
        function<int(int)> find = [&](int x) {
            while (par[x] != x) {
                par[x] = par[par[x]];
                x = par[x];
            }
            return x;
        };
        for (auto& e : edges) par[find(e[0])] = find(e[1]);
        return find(0) == find(n - 1);
    }
};

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */ var validPath = function(n, edges) {
    const par = [];
    for (let i = 0; i < n; i++) par[i] = i;
    const find = (x) => {
        while (par[x] !== x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };
    for (const [a, b] of edges) par[find(a)] = find(b);
    return find(0) === find(n - 1);
};

Find if Path Exists in Graph

Example 1

Example 2

Constraints