LeetCode 1724: Checking Existence of Edge Length Limited Paths II Solution

Master LeetCode problem 1724 (Checking Existence of Edge Length Limited Paths II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1724. Checking Existence of Edge Length Limited Paths II

Hard

Union Find Graph Minimum Spanning Tree

Problem Explanation

Explanation:

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

Add an undirected edge between two nodes with a given weight.
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:

Sort the edges based on their weights.
Initialize the union-find data structure and an additional array to store the query results.
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.
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. :

Solution Code

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;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1724 (Checking Existence of Edge Length Limited Paths II)?

This page provides optimized solutions for LeetCode problem 1724 (Checking Existence of Edge Length Limited Paths II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1724 (Checking Existence of Edge Length Limited Paths II)?

The time complexity for LeetCode 1724 (Checking Existence of Edge Length Limited Paths II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1724 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1724 in Java, C++, or Python.

Back to LeetCode Solutions