Checking Existence of Edge Length Limited Paths II - Solution & Explanation

Problem Overview: You are given a weighted undirected graph and must repeatedly answer queries of the form (p, q, limit). Each query asks whether a path exists between nodes p and q where every edge weight is strictly less than limit. Queries happen after preprocessing, so the solution must answer them quickly.

Approach 1: Per-Query Graph Search (BFS/DFS) (Time: O(Q * (V + E)), Space: O(V))

For every query, run a BFS or DFS starting from node p. Only traverse edges whose weight is less than limit. If node q is reached, the answer is true. This approach directly models the constraint but repeats the same work for each query. With many queries or dense graphs, repeatedly scanning edges becomes expensive.

Approach 2: Offline Queries with Union Find (Time: O((E + Q) log E), Space: O(V))

If all queries are known in advance, sort edges by weight and sort queries by their limit. Incrementally add edges into a Union-Find structure while the edge weight is smaller than the current query limit. After inserting all valid edges, check whether p and q belong to the same component. This technique works well for the single-batch version of the problem but does not handle dynamic queries efficiently because queries must be processed in sorted order.

Approach 3: Minimum Spanning Tree + Binary Lifting (Time: O(E log E + V log V + Q log V), Space: O(V log V))

The key insight comes from the properties of a Minimum Spanning Tree. For any two nodes, the path between them in the MST minimizes the maximum edge weight among all possible paths in the original graph. Build the MST using Kruskal's algorithm and a Union-Find structure. Then preprocess the tree with binary lifting (LCA) while storing the maximum edge weight from each node to its ancestors.

For a query (p, q, limit), compute the maximum edge weight along the MST path between p and q. If that maximum is less than limit, a valid path exists in the original graph. Each query becomes an LCA computation with maximum-edge tracking, which runs in O(log V). The heavy work happens during preprocessing, making queries extremely fast.

Recommended for interviews: The MST + LCA approach is the expected solution. It shows you understand MST bottleneck properties and how to combine them with fast ancestor queries. Mentioning the per-query BFS demonstrates baseline reasoning, while the MST-based preprocessing demonstrates the optimization interviewers look for in hard graph problems.