#1697

Hard

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Checking Existence of Edge Length Limited Paths

Solve the problem of checking if there exists a path between two nodes under edge length constraints using efficient techniques like two-pointer scanning and union-find.

array two pointers union find graph sorting

Problem Statement

You are given an undirected graph with n nodes and an edge list where each edge is represented as [u, v, dis] indicating an edge between nodes u and v with distance dis. Note that there may be multiple edges between the same nodes.

Your task is to determine, for each query [p, q, limit], if there exists a path between nodes p and q such that every edge on the path has a distance strictly less than limit. Return an array where each element corresponds to the result of the respective query, either true or false.

Examples

Example 1

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]

Output: [false,true]

The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16. For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query. For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]

Output: [true,false]

The above figure shows the given graph.

Constraints

2 <= n <= 105
1 <= edgeList.length, queries.length <= 105
edgeList[i].length == 3
queries[j].length == 3
0 <= ui, vi, pj, qj <= n - 1
ui != vi
pj != qj
1 <= disi, limitj <= 109
There may be multiple edges between two nodes.

Solution Approach

Sorting Edges and Queries

Begin by sorting both the edges by their distance and the queries by the path length limit. This allows processing edges progressively, using union-find to determine connectivity as the edges' distances increase.

Union-Find for Connectivity

Union-find is used to track which nodes are connected as we process edges. For each query, only consider edges with distances less than the specified limit. This minimizes unnecessary checks.

Two-Pointer Scanning

Use a two-pointer approach to scan through both sorted edge list and sorted queries simultaneously. This ensures that queries are answered as efficiently as possible, avoiding re-evaluation of the same edges for different queries.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is mainly determined by the sorting steps: sorting the edges takes O(E log E), and sorting the queries takes O(Q log Q). Processing the edges and answering the queries both take linear time. Thus, the overall time complexity is O((E + Q) log Q). The space complexity is dominated by the union-find structure, which is O(n).

What Interviewers Usually Probe

Check the candidate's ability to optimize repeated computations across multiple queries.
Look for a solid understanding of union-find and graph traversal algorithms.
Assess how efficiently the candidate integrates sorting and two-pointer techniques into their solution.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize for multiple queries by not sorting or reordering them properly.
Mismanaging the union-find data structure, leading to unnecessary recomputation of connected components.
Overcomplicating the solution by attempting brute force for each query without leveraging sorted edges.

Follow-up variants

Implementing the solution with a depth-first search (DFS) approach instead of union-find.
Handling cases where the edge distances are extremely large, and the graph is sparse.
Optimizing for very large graphs with a focus on minimizing space complexity.

FAQ

How does two-pointer scanning help with the Checking Existence of Edge Length Limited Paths problem?

Two-pointer scanning allows us to process sorted edges and queries in tandem, efficiently answering multiple queries while avoiding redundant checks for edges already evaluated.

What is the role of union-find in this problem?

Union-find is used to track connectivity between nodes as edges are processed, ensuring we only check edges with distances that meet the query constraints.

What makes the Checking Existence of Edge Length Limited Paths problem hard?

The challenge lies in optimizing for multiple queries and efficiently managing the graph traversal without redundant computations, especially given large input sizes.

What does it mean that the problem involves 'multiple edges between nodes'?

This means that there could be more than one edge between any pair of nodes with different distances. Handling this requires careful edge selection and traversal during query processing.

How can GhostInterview help me optimize the solution for large datasets?

GhostInterview suggests techniques like sorting edges and queries and using efficient data structures such as union-find to ensure the solution remains scalable for large datasets.

terminal

Solution

Solution 1: Offline Queries + Union-Find

According to the problem requirements, we need to judge each query $queries[i]$, that is, to determine whether there is a path with edge weight less than or equal to $limit$ between the two points $a$ and $b$ of the current query.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def distanceLimitedPathsExist(
        self, n: int, edgeList: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        edgeList.sort(key=lambda x: x[2])
        j = 0
        ans = [False] * len(queries)
        for i, (a, b, limit) in sorted(enumerate(queries), key=lambda x: x[1][2]):
            while j < len(edgeList) and edgeList[j][2] < limit:
                u, v, _ = edgeList[j]
                p[find(u)] = find(v)
                j += 1
            ans[i] = find(a) == find(b)
        return ans

Continue Practicing

#1632 rank transform of a matrix #1782 count pairs of nodes #2421 number of good paths