LeetCode 1724: Checking Existence of Edge Length Limited Paths II

Explanation:

The problem requires us to implement a data structure that supports the following operations:

1. Add an undirected edge between two nodes with a given weight.
2. Check if there exists a path between two nodes whose maximum edge weight is less than a given threshold.

To solve this problem efficiently, we can use the Union-Find (Disjoint Set Union) data structure along with sorting the edges based on their weights. We will process the queries in reverse order and maintain the union-find data structure to track the connected components. This approach ensures that we can quickly determine if there exists a path between two nodes with a maximum edge weight less than the given threshold.

Algorithm:

1. Sort the edges based on their weights.
2. Initialize the union-find data structure and an additional array to store the query results.
3. Iterate through the queries in reverse order and process them:
   • For each query, merge the nodes of the edge with the given weight.
   • Check if the start and end nodes are in the same connected component. If they are, update the query result accordingly.
4. Return the final query results.

Time Complexity: O(NlogN + QlogQ + Nα(N)), where N is the number of nodes, Q is the number of queries, logN is the sorting complexity, and α(N) is the inverse Ackermann function. Space Complexity: O(N), where N is the number of nodes. :

class UnionFind {
    int[] parent;
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}

public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
    int q = queries.length;
    boolean[] res = new boolean[q];
    
    int[] idx = new int[q];
    for (int i = 0; i < q; i++) {
        idx[i] = i;
    }
    Arrays.sort(idx, (a, b) -> Integer.compare(queries[b][2], queries[a][2]));
    
    Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
    
    UnionFind uf = new UnionFind(n);
    
    int j = 0;
    for (int i : idx) {
        int[] query = queries[i];
        int limit = query[2];
        while (j < edgeList.length && edgeList[j][2] < limit) {
            uf.union(edgeList[j][0], edgeList[j][1]);
            j++;
        }
        res[i] = uf.find(query[0]) == uf.find(query[1]);
    }
    
    return res;
}