LeetCode 1697 - Checking Existence of Edge Length Limited Paths

This problem gives us an undirected weighted graph with n nodes. Each edge connects two nodes and has a distance value associated with it.

leetcodehardarraytwo-pointersunion-findgraph-theorysorting

LeetCode Problem 1697

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Union-Find, Graph Theory, Sorting

Solution

LeetCode 1697 - Checking Existence of Edge Length Limited Paths

Problem Understanding

This problem gives us an undirected weighted graph with n nodes. Each edge connects two nodes and has a distance value associated with it. We are also given multiple queries, where each query asks whether there exists a path between two nodes such that every edge used in that path has a weight strictly smaller than a given limit.

For a query [p, q, limit], we are not trying to minimize total distance. Instead, we only care whether it is possible to travel from p to q using edges where every individual edge weight is less than limit.

This distinction is extremely important. A path may contain many edges, and the total sum of distances does not matter. The only requirement is that each edge independently satisfies:

edge_weight < limit

The graph may contain multiple edges between the same pair of nodes, and these edges may have different weights. We must treat each edge independently.

The constraints are very large:

  • Up to 10^5 nodes
  • Up to 10^5 edges
  • Up to 10^5 queries

These limits immediately tell us that running a graph traversal for every query independently would likely be too slow. Any algorithm worse than roughly O((E + Q) log N) will struggle.

An important observation is that the query condition is monotonic. If an edge with weight w is allowed for some limit L, then it is also allowed for every larger limit. This property strongly suggests an offline processing strategy using sorting.

Some important edge cases include:

  • Queries where no edges satisfy the limit
  • Multiple edges between the same nodes
  • Disconnected components
  • Limits smaller than all edge weights
  • Limits larger than all edge weights
  • Graphs where connectivity changes gradually as more edges become available

The problem guarantees that:

  • Node indices are valid
  • Nodes in a query are distinct
  • Edge weights and limits are positive
  • The graph may contain cycles and duplicate edges

Approaches

Brute Force Approach

A straightforward solution is to process each query independently.

For every query [p, q, limit], we could construct a subgraph containing only edges whose weights are strictly smaller than limit. Then we run either DFS or BFS from p to determine whether q is reachable.

This approach is correct because it directly models the problem definition. If a path exists in the filtered graph, then every edge on that path satisfies the constraint.

However, the performance is extremely poor for large inputs.

For each query:

  • We may scan all edges to filter valid ones
  • We may traverse most of the graph using BFS or DFS

With up to 10^5 queries and 10^5 edges, this becomes far too expensive.

Optimal Approach, Offline Queries with Union-Find

The key insight is that queries differ only by the allowed edge limit.

Suppose we sort all edges by weight. Then we also sort queries by their limit. As query limits increase, more edges become usable.

Instead of rebuilding the graph for every query, we process queries in ascending order of limit and incrementally add edges whose weights are smaller than the current limit.

To efficiently maintain connectivity, we use the Union-Find data structure, also called Disjoint Set Union, DSU.

Union-Find supports two operations efficiently:

  • Merge two connected components
  • Check whether two nodes belong to the same component

While processing queries in sorted order:

  • Add all edges with weight < limit
  • Union their endpoints
  • Check whether the query nodes belong to the same set

This works because once an edge becomes valid for a smaller limit, it remains valid for all larger limits.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(Q × (E + V)) O(E + V) BFS or DFS for every query
Optimal O(E log E + Q log Q) O(V + Q) Offline sorting with Union-Find

Algorithm Walkthrough

  1. Initialize a Union-Find structure for all n nodes.

Initially, every node belongs to its own connected component because no edges have been added yet. 2. Sort edgeList by edge weight in ascending order.

This allows us to progressively add edges as query limits increase. 3. Attach the original index to every query.

Since sorting changes query order, we must remember each query's original position so we can place answers correctly.

Each query becomes:

[p, q, limit, original_index]
  1. Sort all queries by limit in ascending order.

This ensures we process queries from smallest allowed edge weight to largest. 5. Maintain a pointer into the sorted edge list.

The pointer represents how many edges have already been added into the Union-Find structure. 6. Process queries one by one in sorted order.

For the current query limit:

  • Add every edge whose weight is strictly smaller than the limit
  • Union the edge endpoints
  • Advance the edge pointer

Because edges are sorted, every edge is processed exactly once. 7. After adding all valid edges for the current query, check connectivity.

If the two query nodes have the same root in Union-Find, then a valid path exists. 8. Store the result in the answer array using the query's original index.

This restores the original query ordering required by the problem. 9. Return the final answer array.

Why it works

At any moment during processing, the Union-Find structure contains exactly the edges whose weights are smaller than the current query limit.

Union-Find partitions the graph into connected components using only those allowed edges. Therefore, two nodes belong to the same component if and only if a valid path exists between them under the query constraint.

Because queries are processed in increasing order of limit, edges never need to be removed. Each edge is added once, which gives the algorithm its efficiency.

Python Solution

from typing import List

class Solution:
    def distanceLimitedPathsExist(
        self,
        n: int,
        edgeList: List[List[int]],
        queries: List[List[int]]
    ) -> List[bool]:

        parent = list(range(n))
        rank = [0] * n

        def find(node: int) -> int:
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

        edgeList.sort(key=lambda edge: edge[2])

        indexed_queries = [
            [p, q, limit, index]
            for index, (p, q, limit) in enumerate(queries)
        ]

        indexed_queries.sort(key=lambda query: query[2])

        answers = [False] * len(queries)

        edge_index = 0

        for p, q, limit, original_index in indexed_queries:

            while (
                edge_index < len(edgeList)
                and edgeList[edge_index][2] < limit
            ):
                u, v, _ = edgeList[edge_index]
                union(u, v)
                edge_index += 1

            answers[original_index] = (find(p) == find(q))

        return answers

The implementation begins by creating the Union-Find data structure using two arrays:

  • parent, which stores the representative parent of each node
  • rank, which helps keep the tree shallow during unions

The find function uses path compression. Whenever we search for a node's root, we directly connect intermediate nodes to the root. This greatly improves performance.

The union function uses union by rank. Smaller trees are attached under larger trees to keep the structure balanced.

Next, the edge list is sorted by weight so that edges can be added incrementally in ascending order.

Queries are augmented with their original indices because sorting changes their order.

The main loop processes queries from smallest limit to largest. Before answering a query, we add every edge whose weight is strictly smaller than the query limit.

Once all eligible edges have been merged into the Union-Find structure, connectivity becomes easy to test. If both query nodes share the same root, a valid path exists.

Finally, answers are stored using the original query index and returned in the correct order.

Go Solution

package main

import "sort"

func distanceLimitedPathsExist(n int, edgeList [][]int, queries [][]int) []bool {

	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(node int) int {
		if parent[node] != node {
			parent[node] = find(parent[node])
		}
		return parent[node]
	}

	union := func(a int, b int) {
		rootA := find(a)
		rootB := find(b)

		if rootA == rootB {
			return
		}

		if rank[rootA] < rank[rootB] {
			parent[rootA] = rootB
		} else if rank[rootA] > rank[rootB] {
			parent[rootB] = rootA
		} else {
			parent[rootB] = rootA
			rank[rootA]++
		}
	}

	sort.Slice(edgeList, func(i, j int) bool {
		return edgeList[i][2] < edgeList[j][2]
	})

	type Query struct {
		p      int
		q      int
		limit  int
		index  int
	}

	indexedQueries := make([]Query, len(queries))

	for i, query := range queries {
		indexedQueries[i] = Query{
			p:     query[0],
			q:     query[1],
			limit: query[2],
			index: i,
		}
	}

	sort.Slice(indexedQueries, func(i, j int) bool {
		return indexedQueries[i].limit < indexedQueries[j].limit
	})

	answers := make([]bool, len(queries))

	edgeIndex := 0

	for _, query := range indexedQueries {

		for edgeIndex < len(edgeList) &&
			edgeList[edgeIndex][2] < query.limit {

			u := edgeList[edgeIndex][0]
			v := edgeList[edgeIndex][1]

			union(u, v)

			edgeIndex++
		}

		answers[query.index] = (find(query.p) == find(query.q))
	}

	return answers
}

The Go implementation follows the same logic as the Python solution. The main differences come from language syntax and type handling.

Go does not support nested classes, so the Union-Find logic is implemented using closures.

Queries are represented using a custom Query struct because Go slices do not naturally support heterogeneous tuples like Python lists.

The sort.Slice function is used for sorting both edges and queries.

Since all constraints fit comfortably within Go's int range on modern platforms, integer overflow is not a concern here.

Worked Examples

Example 1

n = 3

edgeList = [
    [0,1,2],
    [1,2,4],
    [2,0,8],
    [1,0,16]
]

queries = [
    [0,1,2],
    [0,2,5]
]

Step 1, Sort edges

Edge Weight
[0,1,2] 2
[1,2,4] 4
[2,0,8] 8
[1,0,16] 16

Step 2, Sort queries by limit

Query Limit Original Index
[0,1,2] 2 0
[0,2,5] 5 1

Initial Union-Find

Node Parent
0 0
1 1
2 2

Process Query [0,1,2]

Allowed edges must satisfy:

weight < 2

No edges qualify.

Connectivity check:

find(0) != find(1)

Answer:

false

Process Query [0,2,5]

Allowed edges must satisfy:

weight < 5

Add edge [0,1,2]

Node Parent
0 0
1 0
2 2

Add edge [1,2,4]

Node Parent
0 0
1 0
2 0

Connectivity check:

find(0) == find(2)

Answer:

true

Final result:

[false, true]

Worked Example 2

n = 5

edgeList = [
    [0,1,10],
    [1,2,5],
    [2,3,9],
    [3,4,13]
]

queries = [
    [0,4,14],
    [1,4,13]
]

Step 1, Sort edges

Edge Weight
[1,2,5] 5
[2,3,9] 9
[0,1,10] 10
[3,4,13] 13

Step 2, Sort queries

Query Limit
[1,4,13] 13
[0,4,14] 14

Process Query [1,4,13]

Add edges with weight < 13:

  • [1,2,5]
  • [2,3,9]
  • [0,1,10]

Current connected component:

0 - 1 - 2 - 3

Node 4 is isolated.

Connectivity check:

find(1) != find(4)

Answer:

false

Process Query [0,4,14]

Add edge:

  • [3,4,13]

Now all nodes are connected.

Connectivity check:

find(0) == find(4)

Answer:

true

Restore original query order:

[true, false]

Complexity Analysis

Measure Complexity Explanation
Time O(E log E + Q log Q) Sorting dominates the runtime
Space O(N + Q) Union-Find arrays and indexed queries

The algorithm sorts the edge list once and sorts the queries once.

Union-Find operations are nearly constant time due to path compression and union by rank. More precisely, they run in amortized O(α(N)), where α is the inverse Ackermann function, which grows extremely slowly.

Each edge is processed exactly once, and each query performs only a few Union-Find operations.

Test Cases

from typing import List

class Solution:
    def distanceLimitedPathsExist(
        self,
        n: int,
        edgeList: List[List[int]],
        queries: List[List[int]]
    ) -> List[bool]:

        parent = list(range(n))
        rank = [0] * n

        def find(node):
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        def union(a, b):
            ra = find(a)
            rb = find(b)

            if ra == rb:
                return

            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1

        edgeList.sort(key=lambda x: x[2])

        indexed_queries = [
            [p, q, limit, i]
            for i, (p, q, limit) in enumerate(queries)
        ]

        indexed_queries.sort(key=lambda x: x[2])

        result = [False] * len(queries)

        edge_index = 0

        for p, q, limit, idx in indexed_queries:

            while edge_index < len(edgeList) and edgeList[edge_index][2] < limit:
                u, v, _ = edgeList[edge_index]
                union(u, v)
                edge_index += 1

            result[idx] = (find(p) == find(q))

        return result

solution = Solution()

# Example 1
assert solution.distanceLimitedPathsExist(
    3,
    [[0,1,2],[1,2,4],[2,0,8],[1,0,16]],
    [[0,1,2],[0,2,5]]
) == [False, True]  # Provided example

# Example 2
assert solution.distanceLimitedPathsExist(
    5,
    [[0,1,10],[1,2,5],[2,3,9],[3,4,13]],
    [[0,4,14],[1,4,13]]
) == [True, False]  # Provided example

# No valid edges
assert solution.distanceLimitedPathsExist(
    2,
    [[0,1,5]],
    [[0,1,5]]
) == [False]  # Strictly less than condition

# Single valid edge
assert solution.distanceLimitedPathsExist(
    2,
    [[0,1,5]],
    [[0,1,6]]
) == [True]  # Edge becomes usable

# Multiple edges between same nodes
assert solution.distanceLimitedPathsExist(
    2,
    [[0,1,10],[0,1,3]],
    [[0,1,5]]
) == [True]  # Smaller edge works

# Disconnected graph
assert solution.distanceLimitedPathsExist(
    4,
    [[0,1,2],[2,3,2]],
    [[0,3,5]]
) == [False]  # Different components

# Large limit connects everything
assert solution.distanceLimitedPathsExist(
    4,
    [[0,1,1],[1,2,2],[2,3,3]],
    [[0,3,100]]
) == [True]  # Entire graph connected

# Query order restoration
assert solution.distanceLimitedPathsExist(
    3,
    [[0,1,2],[1,2,3]],
    [[0,2,4],[0,2,2]]
) == [True, False]  # Results returned in original order

# Cycle graph
assert solution.distanceLimitedPathsExist(
    4,
    [[0,1,1],[1,2,1],[2,3,1],[3,0,1]],
    [[0,2,2]]
) == [True]  # Multiple possible paths

# Limit too small for all paths
assert solution.distanceLimitedPathsExist(
    3,
    [[0,1,4],[1,2,4]],
    [[0,2,4]]
) == [False]  # Equality is not allowed

Test Case Summary

Test Why
Example 1 Verifies basic functionality
Example 2 Verifies incremental edge addition
No valid edges Tests strict inequality handling
Single valid edge Simplest connected graph
Multiple duplicate edges Ensures smallest valid edge works
Disconnected graph Verifies unreachable nodes
Large limit connects everything Tests fully connected behavior
Query order restoration Ensures sorting does not break output order
Cycle graph Verifies correctness with multiple paths
Limit too small Confirms equality is excluded

Edge Cases

Strictly Less Than vs Less Than or Equal

One of the most common mistakes is accidentally treating the condition as:

edge_weight <= limit

instead of:

edge_weight < limit

This changes the behavior significantly. For example, an edge with weight 5 cannot be used when the limit is also 5.

The implementation handles this correctly using:

while edge_weight < limit:

rather than <=.

Multiple Edges Between the Same Nodes

The graph may contain several edges connecting the same pair of nodes with different weights.

A naive implementation might incorrectly overwrite edges or assume uniqueness.

This solution processes every edge independently after sorting. If any edge satisfies the limit constraint, it can contribute to connectivity.

Queries Arriving in Arbitrary Order

Queries are sorted internally by limit for efficiency, but the output must match the original query order.

Without storing original indices, results would be returned in sorted order instead of input order.

The implementation solves this by augmenting each query with its original index and writing answers back into the correct position.