LeetCode Solutions Blog

Checking Existence of Edge Length Limited Paths

Number: 1815

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an undirected graph with n nodes represented by edgeList, where each edge is given in the form [u, v, weight], determine for each query [p, q, limit] whether there exists a path from node p to q such that every edge on the path has a weight strictly less than limit. Note that there may be multiple edges between the same pair of nodes.

Key Insights

Sort both the edgeList and the queries by the weight and limit respectively.
Use a Union Find (Disjoint Set Union) data structure to efficiently connect nodes.
Process queries offline: while increasing the limit, add all edges from the sorted edgeList with weight less than the current query limit. Then check connectivity.
Handling multiple queries and edges in a single sweep ensures efficiency.

Space and Time Complexity

Time Complexity: O(E log E + Q log Q + (E + Q) * α(n))
Space Complexity: O(n + E + Q)
(Note: α(n) is the inverse Ackermann function which is almost constant.)

Solution

We solve the problem by first sorting the edgeList based on the edge weights and the queries based on their limit. We then iterate through the queries in increasing order of limit. For each query, we union all edges from the sorted edgeList that have weights strictly less than the query's limit. After processing the appropriate edges, we check if the two nodes in the query belong to the same connected component by using the Union Find data structure. This approach is efficient given the constraints and allows us to answer each query in nearly constant time after sorting.

Code Solutions

# Python solution with line-by-line comments

class UnionFind:
    def __init__(self, n):
        # Initialize the parent array for each node
        self.parent = list(range(n))
    
    def find(self, x):
        # Find the root of x with path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union the sets of x and y
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY

def checkEdgeExistence(n, edgeList, queries):
    # Append original index to each query for result ordering
    queries_with_index = [ (p, q, limit, i) for i, (p, q, limit) in enumerate(queries) ]
    # Sort queries based on limit
    queries_with_index.sort(key=lambda x: x[2])
    # Sort edgeList based on edge weight
    edgeList.sort(key=lambda x: x[2])
    
    # Create a union-find structure
    uf = UnionFind(n)
    answer = [False] * len(queries)
    edge_index = 0
    # Process each query in increasing order of limit
    for p, q, limit, query_index in queries_with_index:
        # Add all edges with weight less than limit to the union-find
        while edge_index < len(edgeList) and edgeList[edge_index][2] < limit:
            u, v, weight = edgeList[edge_index]
            uf.union(u, v)
            edge_index += 1
        # After union operations, check if p and q are connected
        if uf.find(p) == uf.find(q):
            answer[query_index] = True
    return answer

# Example usage:
if __name__ == "__main__":
    n = 3
    edgeList = [[0, 1, 2], [1, 2, 4], [2, 0, 8], [1, 0, 16]]
    queries = [[0, 1, 2], [0, 2, 5]]
    print(checkEdgeExistence(n, edgeList, queries))  # Output: [False, True]