How do you solve Checking Existence of Edge Length Limited Paths on LeetCode?

Checking Existence of Edge Length Limited Paths (LeetCode #1697) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O((n + q) log n + q log q) time complexity and O(n) space complexity. Key insight: Using union-find allows us to efficiently manage connected components as we process edges and queries.

What is the brute force solution for Checking Existence of Edge Length Limited Paths?

The brute force approach for Checking Existence of Edge Length Limited Paths is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each query by performing a depth-first search (DFS) or breadth-first search (BFS) for each pair of nodes in the query. This method is straightforward but inefficient for large graphs. The optimal Optimal Solution approach improves this to O((n + q) log n + q log q).

What algorithm or data structure is used to solve Checking Existence of Edge Length Limited Paths?

Checking Existence of Edge Length Limited Paths uses the following concepts: Array, Two Pointers, Union-Find, Graph Theory, Sorting. The recommended patterns to study are: Union-Find, Sorting.

What are the interview tips for Checking Existence of Edge Length Limited Paths?

Always consider how you can optimize your approach by reducing repeated work. Be clear about the data structures you choose and why they are suitable for the problem. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Checking Existence of Edge Length Limited Paths?

Failing to properly implement the union-find structure, leading to incorrect connectivity checks. Not sorting edges and queries, which can lead to inefficiencies and incorrect results.

#1697

Checking Existence of Edge Length Limited Paths

Hard

ArrayTwo PointersUnion-FindGraph TheorySortingUnion-FindSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O((n + q) log n + q log q)
Space	O(1)	O(n)

💡

Intuition

Time O((n + q) log n + q log q)Space O(n)

The optimal approach uses a union-find (disjoint set union) structure to efficiently group nodes based on edge distances. By sorting edges and queries, we can process them in a single pass, avoiding repeated computations.

⚙️

Algorithm

4 steps

1Step 1: Sort the edgeList by distance and the queries by limit.
2Step 2: Initialize a union-find structure to manage connected components.
3Step 3: Iterate through the sorted queries and edges, adding edges to the union-find structure as long as their distance is less than the current query's limit.
4Step 4: For each query, check if the two nodes are in the same connected component using the union-find structure.

solution.py38 lines

1# Full working Python code
2class UnionFind:
3    def __init__(self, n):
4        self.parent = list(range(n))
5        self.rank = [1] * n
6    
7    def find(self, x):
8        if self.parent[x] != x:
9            self.parent[x] = self.find(self.parent[x])
10        return self.parent[x]
11    
12    def union(self, x, y):
13        rootX = self.find(x)
14        rootY = self.find(y)
15        if rootX != rootY:
16            if self.rank[rootX] > self.rank[rootY]:
17                self.parent[rootY] = rootX
18            elif self.rank[rootX] < self.rank[rootY]:
19                self.parent[rootX] = rootY
20            else:
21                self.parent[rootY] = rootX
22                self.rank[rootX] += 1
23
24
25def canReach(n, edgeList, queries):
26    edgeList.sort(key=lambda x: x[2])
27    queries = sorted(enumerate(queries), key=lambda x: x[1][2])
28    uf = UnionFind(n)
29    result = [False] * len(queries)
30    edgeIndex = 0
31    
32    for i, (p, q, limit) in queries:
33        while edgeIndex < len(edgeList) and edgeList[edgeIndex][2] < limit:
34            uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1])
35            edgeIndex += 1
36        result[i] = uf.find(p) == uf.find(q)
37    return result
38

ℹ

Complexity note: The complexity is dominated by the sorting steps, which are O(n log n) for edges and O(q log q) for queries. The union-find operations are nearly constant time due to path compression.

1Using union-find allows us to efficiently manage connected components as we process edges and queries.
2Sorting edges and queries helps to minimize redundant checks and ensures we only consider relevant edges for each query.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.