Skip to main content
Talentd

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

HardPremiumFree on FleetCodeUnion FindGraphMinimum Spanning Tree8 min readAsked at: Google, Oscar Health
Practice this problem

Problem Statement

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes, and the graph may not be connected.

Implement the DistanceLimitedPathsExist class:

  • DistanceLimitedPathsExist(int n, int[][] edgeList) Initializes the class with an undirected graph.
  • boolean query(int p, int q, int limit) Returns true if there exists a path from p to q such that each edge on the path has a distance strictly less than limit, and otherwise false.

 

Example 1:

Input
["DistanceLimitedPathsExist", "query", "query", "query", "query"]
[[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]]
Output
[null, true, false, true, false]

Explanation
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
distanceLimitedPathsExist.query(2, 3, 2); // return true. There is an edge from 2 to 3 of distance 1, which is less than 2.
distanceLimitedPathsExist.query(1, 3, 3); // return false. There is no way to go from 1 to 3 with distances strictly less than 3.
distanceLimitedPathsExist.query(2, 0, 3); // return true. There is a way to go from 2 to 0 with distance < 3: travel from 2 to 3 to 0.
distanceLimitedPathsExist.query(0, 5, 6); // return false. There are no paths from 0 to 5.

 

Constraints:

  • 2 <= n <= 104
  • 0 <= edgeList.length <= 104
  • edgeList[i].length == 3
  • 0 <= ui, vi, p, q <= n-1
  • ui != vi
  • p != q
  • 1 <= disi, limit <= 109
  • At most 104 calls will be made to query.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Per-query BFS/DFSO(Q * (V + E))O(V)Small graphs or very few queries
Offline Queries with Union-FindO((E + Q) log E)O(V)When all queries are known beforehand and can be sorted
MST + LCA (Binary Lifting)O(E log E + V log V + Q log V)O(V log V)Best choice for many online queries after preprocessing

Video Solution

1724. Checking Existence of Edge Length Limited Paths II (Leetcode Hard) • Programming Live with Larry • 275 views views

Frequently Asked Questions

Is Checking Existence of Edge Length Limited Paths II easy or hard?
LeetCode classifies this problem as Hard. The challenge is recognizing the MST bottleneck property and combining it with LCA preprocessing to support fast repeated queries. Implementing Union-Find and binary lifting correctly is required for an optimal solution.
Checking Existence of Edge Length Limited Paths II Python/Java solution
Most implementations build the MST using Union-Find, then preprocess parent and maximum-edge tables for binary lifting. The query method climbs the tree to the LCA while tracking the maximum edge weight. The same algorithm translates cleanly across Python, Java, C++, Go, and TypeScript.
What is the best approach for Checking Existence of Edge Length Limited Paths II?
The optimal approach builds a Minimum Spanning Tree using Kruskal's algorithm and then preprocesses the tree using binary lifting for Lowest Common Ancestor queries. For each query, compute the maximum edge weight along the path between the two nodes in the MST. If that value is less than the limit, a valid path exists. This gives O(log n) query time after preprocessing.
Is Checking Existence of Edge Length Limited Paths II asked at Google/Amazon/Meta?
Problems combining Union-Find, Minimum Spanning Trees, and LCA preprocessing frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of graph connectivity, MST properties, and fast query processing after preprocessing.
What data structure is used in Checking Existence of Edge Length Limited Paths II?
The solution uses several core structures: Union-Find for building the Minimum Spanning Tree with Kruskal's algorithm, adjacency lists to store the MST, and binary lifting tables for Lowest Common Ancestor queries. These structures allow efficient preprocessing and fast query responses.
What is the time complexity of Checking Existence of Edge Length Limited Paths II?
The optimized solution runs in O(E log E + V log V + Q log V). Building the MST requires sorting edges, which takes O(E log E). LCA preprocessing takes O(V log V), and each query is answered in O(log V) time by checking the maximum edge weight along the MST path.
How to solve Checking Existence of Edge Length Limited Paths II in O(log n) per query?
First construct a Minimum Spanning Tree from the graph. Then preprocess the tree using binary lifting to compute Lowest Common Ancestors while storing the maximum edge weight to each ancestor. Each query checks the maximum edge weight on the path between two nodes in O(log n). If the maximum weight is less than the limit, the path satisfies the constraint.

Ready to solve this problem?

Practice Checking Existence of Edge Length Limited Paths II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Checking Existence of Edge Length Limited Paths

Next

Minimum Score of a Path Between Two Cities