Skip to main content
Talentd

Checking Existence of Edge Length Limited Paths - Solution & Explanation

HardArrayTwo PointersUnion FindGraph22 min readAsked at: Microsoft, Uber, Google
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.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

 

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]
Explanation: 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]
Explanation: 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.

Approach Overview

Problem Overview: You are given an undirected weighted graph and several queries. Each query asks whether two nodes can be connected using only edges whose weight is strictly less than a given limit. For every query, return true if such a path exists, otherwise false.

Approach 1: Union-Find with Sorting (O((E + Q) log E) time, O(N) space)

The key idea is to process queries offline by sorting both the edges and the queries by edge weight limit. Instead of checking each query independently, sort the edgeList by weight and sort queries by their limit. Then gradually add edges into a Union-Find structure while their weights remain below the current query’s limit. Once all eligible edges are merged, simply check if the two query nodes belong to the same connected component. This works because connectivity only increases as you add edges in increasing weight order. The Union Find structure provides nearly constant-time find and union operations with path compression and union by rank. Sorting drives the overall complexity, giving O((E + Q) log E) time and O(N) space.

Approach 2: Kruskal's Algorithm Modification (O((E + Q) log E) time, O(N) space)

This approach interprets the problem through the lens of minimum spanning tree construction. Kruskal’s algorithm processes edges in ascending order of weight and connects components using a Union-Find. For each query limit, you effectively simulate running Kruskal until the edge weight reaches that limit. All edges smaller than the limit are merged into the structure. After those merges, checking connectivity between the two query nodes answers the query instantly. Conceptually this is identical to the previous method but framed as a partial MST build for each query threshold. This perspective is helpful if you already understand Kruskal’s algorithm for graph connectivity problems. Sorting the edges and queries ensures efficient processing, while the disjoint set structure maintains components.

Both approaches rely heavily on ordering edges by weight. Efficient preprocessing with sorting ensures edges are added exactly once and queries are answered without repeated graph traversal.

Recommended for interviews: The Union-Find with sorted queries approach is what most interviewers expect. It shows you recognize that queries can be processed offline and that dynamic connectivity can be handled efficiently with a disjoint set. Explaining the brute-force idea (running a constrained BFS/DFS per query) demonstrates baseline understanding, but switching to the sorted Union-Find solution shows strong algorithmic insight.

Approach 1: Union-Find with Sorting

This approach is based on using a Union-Find (Disjoint Set Union) data structure, which allows us to efficiently keep track of connected components in the graph. The strategy involves sorting both the edges and the queries based on the edge weights and the query limits, respectively. By processing these sorted lists, we can incrementally add edges to the Union-Find structure and query the connectivity status effectively.

This Python code implements the Union-Find with Path Compression technique. Initially, we sort the edgeList by distance and the queries by their limit. As we iterate over each query, we add edges to the Union-Find structure that are below the given query's limit. Then, we check if the specified nodes in the query belong to the same connected component.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Kruskal's Algorithm Modification

This approach involves modifying Kruskal's Minimum Spanning Tree algorithm to answer multiple queries about path existence. We leverage the intrinsic nature of Kruskal's algorithm which builds an MST (or a union-find structured graph) incrementally. For each query sorted by limit, we add edges with weight less than the limit to the union-find structure and check if two nodes are connected.

This Python code uses a slight modification of Kruskal's algorithm. We use the union-find data structure to progressively add edges before each query is processed, sorted by their limit. It essentially mimics building a Minimum Spanning Tree to answer each query about connectivity efficiently.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: 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.

The connectivity of two points can be determined by a union-find set. Moreover, since the order of queries does not affect the result, we can sort all queries in ascending order by limit, and also sort all edges in ascending order by edge weight.

Then for each query, we start from the edge with the smallest weight, add all edges with weights strictly less than limit to the union-find set, and then use the query operation of the union-find set to determine whether the two points are connected.

The time complexity is O(m times log m + q times log q), where m and q are the number of edges and queries, respectively.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find with Sorting

Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)

Kruskal's Algorithm Modification

Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)

Offline Queries + Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BFS/DFS per QueryO(Q * (N + E))O(N + E)Small graphs or when constraints are tiny and implementation simplicity matters
Union-Find with Sorted QueriesO((E + Q) log E)O(N)Best general solution for large graphs and many queries
Modified Kruskal ProcessingO((E + Q) log E)O(N)Useful when reasoning about MST construction or weight-ordered connectivity

Video Solution

Checking Existence of Edge Length Limited Paths | Leetcode - 1697 | DSU | GOOGLE | Explanation • codestorywithMIK • 9,009 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Checking Existence of Edge Length Limited Paths easy or hard?
This problem is classified as Hard because it combines graph connectivity, offline query processing, and Union-Find optimization. The challenge is recognizing that queries should be sorted and processed incrementally rather than solved independently.
Checking Existence of Edge Length Limited Paths Python or Java solution
Python, Java, C++, JavaScript, and C# implementations typically follow the same pattern: sort edges, sort queries with original indices, process edges incrementally, and use a Union-Find structure to test connectivity. The logic remains identical across languages.
How to solve Checking Existence of Edge Length Limited Paths efficiently?
Sort the edge list by weight and sort queries by their distance limit. Use a Union-Find data structure and keep adding edges whose weights are smaller than the current query limit. After inserting eligible edges, check if the query’s two nodes share the same parent in the disjoint set.
What is the best approach for Checking Existence of Edge Length Limited Paths?
The most efficient approach uses Union-Find with offline query processing. Sort edges by weight and sort queries by their limit. Gradually union edges whose weights are smaller than the query limit, then check if the two nodes belong to the same component. This reduces repeated graph traversals and runs in O((E + Q) log E) time.
Is Checking Existence of Edge Length Limited Paths asked at Google/Amazon/Meta?
Graph connectivity with constraints and Union-Find problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving offline queries, dynamic connectivity, or Kruskal-style processing are common in senior-level algorithm interviews.
What data structure is used in Checking Existence of Edge Length Limited Paths?
The core data structure is Union-Find (Disjoint Set Union). It efficiently maintains connected components while edges are added in sorted order. Path compression and union by rank keep operations nearly constant time.
What is the time complexity of Checking Existence of Edge Length Limited Paths?
The optimal solution runs in O((E + Q) log E) time due to sorting the edges and queries. Union-Find operations such as union and find run in nearly constant amortized time with path compression. Space complexity is O(N) for maintaining the disjoint set structure.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Checking Existence of Edge Length Limited Paths II

Next

Minimum Score of a Path Between Two Cities