1697. Checking Existence of Edge Length Limited Paths

Idea

This problem at first looks a lot like a shortest path problem, but the test case size(\(10^5\)) seems to be too big.

Another observation is that the problem doesn’t really ask for shortest path, instead it asks if the max weight along the path is smaller than something, (hopefully) this relaxes the problem a little bit.

As there is no easy way to find out the max path weight given two random nodes in the graph(probably just DFS and BFS, which result in \(n^2\) time complexity, Floyd-Warshall algorithm has \(n^3\)), we try something else.

We have edge list with weight and queries with weight, and we want to find if two nodes are connected given a max path weight. Then how about we try to connect only edges that meet the weight requirement? If query[2] is 10, we only “connect” the graph using edges that has weight less than 10, then the problem is simplified to:

at this moment, are the two nodes connected?

We have many ways to solve this, Union Find is the one I choose!

Steps

Sort edge list by weight, and we start from the query with smallest weight requirement.

Manipulate the queries a bit, pair each query with its original index, and sort it by weight, so later we can put the answer to the correct position.

Loop through (the new) queries, and go through all the edges which have weight less than query[2], union the nodes, and find if the two nodes are connected, fill answer using the original index.

Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        uf=UnionFind(n)
        edgeList.sort(key=lambda x:x[2])
        res=[False for _ in range(len(queries))]
        # queries_pair
        qp=[] 
        for i,query in enumerate(queries):
            qp.append((query,i))
        qp.sort(key=lambda x:x[0][2])

        qp_pointer=0
        el_pointer=0
        while qp_pointer<len(qp):
            query,idx=qp[qp_pointer]
            # only union nodes that have edge weight strictly less than current query weight
            # we can union in sequence bcuz edge list has been sorted by weight
            while el_pointer<len(edgeList) and edgeList[el_pointer][2]<query[2]:
                start,end,_ = edgeList[el_pointer]
                uf.union(start,end)
                el_pointer+=1
            res[idx]=uf.find(query[0])==uf.find(query[1])
            qp_pointer+=1
        return res

# standard UF
class UnionFind:
    def __init__(self,n):
        self.roots=[i for i in range(n)]
        self.ranks=[1 for _ in range(n)]
    
    def find(self,x):
        xr=self.roots[x]
        if xr==x:
            return xr
        self.roots[x]=self.find(xr)
        return self.roots[x]
    
    def union(self,x,y):
        xr=self.find(x)
        yr=self.find(y)
        if xr==yr:
            return 
        if self.ranks[xr]>self.ranks[yr]:
            self.roots[yr]=xr
        elif self.ranks[xr]<self.ranks[yr]:
            self.roots[xr]=yr
        else:
            self.roots[xr]=yr
            self.ranks[yr]+=1

End

Btw GPT-4’s solution uses Floyd-Warshall algorithm and results in TLE 🤣

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def path_within_limits(n, edgeList, queries):
    # Initialize a graph representation using adjacency matrix
    graph = [[float('inf')] * n for _ in range(n)]
    
    # Populate the graph with edge distances
    for u, v, dis in edgeList:
        graph[u][v] = min(graph[u][v], dis)
        graph[v][u] = min(graph[v][u], dis)

    # Apply the Floyd-Warshall algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], max(graph[i][k], graph[k][j]))

    # Answer the queries
    result = []
    for p, q, limit in queries:
        result.append(graph[p][q] < limit)

    return result

1.jpeg