LeetCode Problem 1724

Difficulty: 🔴 Hard
Topics: Depth-First Search, Union-Find, Graph Theory, Design, Sorting, Heap (Priority Queue), Minimum Spanning Tree

Solution

LeetCode 1724 - Checking Existence of Edge Length Limited Paths II

Problem Understanding

This problem gives us an undirected weighted graph with n nodes and a list of edges. Each edge connects two nodes and has an associated distance value. The graph may contain multiple edges between the same pair of nodes, and it may also be disconnected.

We must design a class named DistanceLimitedPathsExist that supports two operations:

1. Initialization with the graph.
2. Repeated queries asking whether two nodes are connected by a path where every edge on the path has weight strictly smaller than a given limit.

The important detail is the phrase "strictly less than limit". If an edge weight equals the limit, that edge cannot be used.

For a query query(p, q, limit), we must determine whether there exists any valid path from node p to node q such that every edge on that path satisfies:

$$edgeWeight < limit$$

The graph is static after construction. No edges are added or removed during queries.

The constraints are important:

• n <= 10^4
• edgeList.length <= 10^4
• Up to 10^4 queries

A naive graph traversal for every query would potentially cost:

$$O(Q \times (V + E))$$

which can become too slow in worst case scenarios.

The key observation is that all queries are asking about connectivity under different edge weight thresholds. This suggests preprocessing and efficient connectivity structures, rather than repeatedly searching the graph from scratch.

Several edge cases are important:

• The graph may be disconnected.
• Multiple edges may exist between the same nodes.
• A valid path may require several small edges instead of one direct edge.
• The limit is strict, not inclusive.
• Queries may ask about nodes with no possible connection at all.

Because the graph is static and queries are numerous, preprocessing is the correct direction.

Approaches

Brute Force Approach

The most direct solution is to process each query independently using DFS or BFS.

For a query (p, q, limit):

1. Start DFS/BFS from p.
2. Only traverse edges whose weight is strictly less than limit.
3. If q is reachable, return true.
4. Otherwise return false.

This works because graph traversal explores exactly the valid paths allowed under the query constraint.

However, the performance is poor. Each query may scan nearly all vertices and edges. With up to 10^4 queries and 10^4 edges, worst case complexity becomes:

$$O(Q \times (V + E))$$

which can approach 10^8 operations.

This is too expensive for repeated queries.

Optimal Approach

The key insight is that connectivity changes only when new edges become allowed.

Suppose we sort all edges by weight. For a limit L, every edge with weight < L is usable, while all others are forbidden.

If we progressively add edges from smallest weight to largest weight using Union Find, then for any limit we can quickly determine whether two nodes belong to the same connected component.

The challenge is that queries arrive online, not offline. We cannot sort queries and process them once.

To support fast repeated queries, we preprocess a Minimum Spanning Forest using Kruskal's algorithm and then build binary lifting structures for Lowest Common Ancestor style queries.

A crucial graph property is:

If two nodes are connected using edges smaller than limit, then the maximum edge weight on the path between them in the MST is also smaller than limit.

Therefore:

1. Build the Minimum Spanning Forest.
2. Precompute ancestors and maximum edge weights using binary lifting.
3. For each query:

• Check whether nodes are connected.
• Find the maximum edge weight on the MST path between them.
• Return whether that maximum is < limit.

This reduces each query to logarithmic time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Q × (V + E))	O(V + E)	DFS/BFS for every query
Optimal	O(E log E + V log V + Q log V)	O(V log V)	MST + Union Find + Binary Lifting

Algorithm Walkthrough

Step 1: Sort All Edges by Weight

We first sort the edges in non decreasing order of distance.

This is required for Kruskal's algorithm, which constructs a Minimum Spanning Forest by always choosing the smallest available edge that connects two different components.

Step 2: Build a Minimum Spanning Forest Using Union Find

We initialize a Union Find structure.

Then we iterate through the sorted edges:

1. For each edge (u, v, w),
2. If u and v belong to different components,
3. Merge them,
4. Add the edge to the MST adjacency list.

This creates a forest because the original graph may be disconnected.

The MST preserves the minimum possible maximum edge between nodes, which is exactly the property needed for threshold connectivity queries.

Step 3: Prepare Binary Lifting Tables

We perform DFS from every unvisited node in the forest.

During DFS we record:

• depth[node]
• parent[node][0]
• maxEdge[node][0]

where:

• parent[node][0] is the immediate parent
• maxEdge[node][0] is the edge weight to the parent

Then we build higher ancestor tables:

$$parent[node][k]$$

which represents the 2^k ancestor.

Similarly:

$$maxEdge[node][k]$$

stores the maximum edge weight encountered when climbing 2^k steps upward.

This preprocessing enables logarithmic path queries.

Step 4: Store Connected Components

After Kruskal construction, the Union Find already knows which nodes belong to the same connected component.

If two nodes are disconnected, every query between them immediately returns false.

Step 5: Process a Query

For query (p, q, limit):

1. If p and q are not connected, return false.
2. Lift the deeper node upward until both nodes are at the same depth.
3. While lifting, track the maximum edge weight encountered.
4. Lift both nodes upward together until their ancestors match.
5. Include the final edges leading to the LCA.
6. The result is the maximum edge weight on the MST path.
7. Return whether:

$$maxWeight < limit$$

Why it works

The correctness relies on a classic MST property:

For any two nodes, the path between them in the Minimum Spanning Tree minimizes the maximum edge weight among all possible paths in the original graph.

Therefore, if the maximum edge weight on the MST path is smaller than limit, then a valid path exists in the original graph. Conversely, if the MST path contains an edge with weight at least limit, no valid path can exist.

This allows every query to be reduced to checking the maximum edge on one tree path.

Python Solution

from typing import List
import math

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return False

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

        return True

class DistanceLimitedPathsExist:

    def __init__(self, n: int, edgeList: List[List[int]]):
        self.n = n
        self.LOG = math.ceil(math.log2(max(2, n)))

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

        self.graph = [[] for _ in range(n)]

        self.uf = UnionFind(n)

        for u, v, w in edgeList:
            if self.uf.union(u, v):
                self.graph[u].append((v, w))
                self.graph[v].append((u, w))

        self.depth = [0] * n
        self.parent = [[-1] * self.LOG for _ in range(n)]
        self.max_edge = [[0] * self.LOG for _ in range(n)]

        visited = [False] * n

        for node in range(n):
            if not visited[node]:
                self._dfs(node, -1, 0, 0, visited)

        for j in range(1, self.LOG):
            for node in range(n):
                prev_parent = self.parent[node][j - 1]

                if prev_parent != -1:
                    self.parent[node][j] = self.parent[prev_parent][j - 1]

                    self.max_edge[node][j] = max(
                        self.max_edge[node][j - 1],
                        self.max_edge[prev_parent][j - 1]
                    )

    def _dfs(
        self,
        node: int,
        par: int,
        depth: int,
        weight: int,
        visited: List[bool]
    ) -> None:
        visited[node] = True

        self.depth[node] = depth
        self.parent[node][0] = par
        self.max_edge[node][0] = weight

        for neighbor, edge_weight in self.graph[node]:
            if not visited[neighbor]:
                self._dfs(
                    neighbor,
                    node,
                    depth + 1,
                    edge_weight,
                    visited
                )

    def query(self, p: int, q: int, limit: int) -> bool:
        if self.uf.find(p) != self.uf.find(q):
            return False

        maximum = 0

        if self.depth[p] < self.depth[q]:
            p, q = q, p

        diff = self.depth[p] - self.depth[q]

        for bit in range(self.LOG):
            if diff & (1 << bit):
                maximum = max(maximum, self.max_edge[p][bit])
                p = self.parent[p][bit]

        if p == q:
            return maximum < limit

        for bit in range(self.LOG - 1, -1, -1):
            if self.parent[p][bit] != self.parent[q][bit]:
                maximum = max(maximum, self.max_edge[p][bit])
                maximum = max(maximum, self.max_edge[q][bit])

                p = self.parent[p][bit]
                q = self.parent[q][bit]

        maximum = max(maximum, self.max_edge[p][0])
        maximum = max(maximum, self.max_edge[q][0])

        return maximum < limit

The implementation starts by constructing a Minimum Spanning Forest using Kruskal's algorithm. Union Find efficiently determines whether an edge connects two different components.

The adjacency list stores only MST edges, not all original edges. This is important because the MST path preserves the minimum possible bottleneck edge.

Depth first search initializes the binary lifting tables. Each node records:

• its parent
• its depth
• the maximum edge to ancestors

The preprocessing phase builds powers of two ancestors so queries can jump upward logarithmically.

The query method first checks connectivity. If the nodes are disconnected, the answer is immediately false.

Otherwise, it computes the maximum edge weight along the MST path using binary lifting. The final comparison against limit determines the answer.

Go Solution

package main

import (
	"math"
	"sort"
)

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)

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

	return &UnionFind{
		parent: parent,
		rank:   rank,
	}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(a, b int) bool {
	rootA := uf.Find(a)
	rootB := uf.Find(b)

	if rootA == rootB {
		return false
	}

	if uf.rank[rootA] < uf.rank[rootB] {
		rootA, rootB = rootB, rootA
	}

	uf.parent[rootB] = rootA

	if uf.rank[rootA] == uf.rank[rootB] {
		uf.rank[rootA]++
	}

	return true
}

type Edge struct {
	to     int
	weight int
}

type DistanceLimitedPathsExist struct {
	n       int
	log     int
	graph   [][]Edge
	depth   []int
	parent  [][]int
	maxEdge [][]int
	uf      *UnionFind
}

func Constructor(n int, edgeList [][]int) DistanceLimitedPathsExist {
	logVal := int(math.Ceil(math.Log2(float64(max(2, n)))))

	graph := make([][]Edge, n)

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

	uf := NewUnionFind(n)

	for _, edge := range edgeList {
		u, v, w := edge[0], edge[1], edge[2]

		if uf.Union(u, v) {
			graph[u] = append(graph[u], Edge{v, w})
			graph[v] = append(graph[v], Edge{u, w})
		}
	}

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

	for i := 0; i < n; i++ {
		parent[i] = make([]int, logVal)
		maxEdge[i] = make([]int, logVal)

		for j := 0; j < logVal; j++ {
			parent[i][j] = -1
		}
	}

	obj := DistanceLimitedPathsExist{
		n:       n,
		log:     logVal,
		graph:   graph,
		depth:   make([]int, n),
		parent:  parent,
		maxEdge: maxEdge,
		uf:      uf,
	}

	visited := make([]bool, n)

	for i := 0; i < n; i++ {
		if !visited[i] {
			obj.dfs(i, -1, 0, 0, visited)
		}
	}

	for j := 1; j < logVal; j++ {
		for node := 0; node < n; node++ {
			prevParent := obj.parent[node][j-1]

			if prevParent != -1 {
				obj.parent[node][j] = obj.parent[prevParent][j-1]

				obj.maxEdge[node][j] = max(
					obj.maxEdge[node][j-1],
					obj.maxEdge[prevParent][j-1],
				)
			}
		}
	}

	return obj
}

func (this *DistanceLimitedPathsExist) dfs(
	node int,
	par int,
	depth int,
	weight int,
	visited []bool,
) {
	visited[node] = true

	this.depth[node] = depth
	this.parent[node][0] = par
	this.maxEdge[node][0] = weight

	for _, edge := range this.graph[node] {
		if !visited[edge.to] {
			this.dfs(
				edge.to,
				node,
				depth+1,
				edge.weight,
				visited,
			)
		}
	}
}

func (this *DistanceLimitedPathsExist) Query(
	p int,
	q int,
	limit int,
) bool {
	if this.uf.Find(p) != this.uf.Find(q) {
		return false
	}

	maximum := 0

	if this.depth[p] < this.depth[q] {
		p, q = q, p
	}

	diff := this.depth[p] - this.depth[q]

	for bit := 0; bit < this.log; bit++ {
		if diff&(1<<bit) != 0 {
			maximum = max(maximum, this.maxEdge[p][bit])
			p = this.parent[p][bit]
		}
	}

	if p == q {
		return maximum < limit
	}

	for bit := this.log - 1; bit >= 0; bit-- {
		if this.parent[p][bit] != this.parent[q][bit] {
			maximum = max(maximum, this.maxEdge[p][bit])
			maximum = max(maximum, this.maxEdge[q][bit])

			p = this.parent[p][bit]
			q = this.parent[q][bit]
		}
	}

	maximum = max(maximum, this.maxEdge[p][0])
	maximum = max(maximum, this.maxEdge[q][0])

	return maximum < limit
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation mirrors the Python logic closely. Slices are used for adjacency lists and lifting tables. Integer overflow is not a concern because edge weights fit comfortably within Go's int limits on modern platforms.

The recursive DFS initializes binary lifting data. The max helper function simplifies repeated maximum comparisons.

Worked Examples

Example 1

Input:

n = 6
edgeList = [
  [0,2,4],
  [0,3,2],
  [1,2,3],
  [2,3,1],
  [4,5,5]
]

Step 1: Sort Edges

Edge	Weight
(2,3)	1
(0,3)	2
(1,2)	3
(0,2)	4
(4,5)	5

Step 2: Build MST

Add (2,3,1)

Components:

• {2,3}

Add (0,3,2)

Components:

• {0,2,3}

Add (1,2,3)

Components:

• {0,1,2,3}

Skip (0,2,4) because it creates a cycle.

Add (4,5,5)

Components:

• {0,1,2,3}
• {4,5}

Query: query(2,3,2)

Path:

• 2 -> 3

Maximum edge:

• 1

Check:

$$1 < 2$$

Result: true

Query: query(1,3,3)

Path:

• 1 -> 2 -> 3

Edge weights:

• 3, 1

Maximum:

• 3

Check:

$$3 < 3$$

False because the comparison is strict.

Result: false

Query: query(2,0,3)

Path:

• 2 -> 3 -> 0

Edge weights:

• 1, 2

Maximum:

• 2

Check:

$$2 < 3$$

Result: true

Query: query(0,5,6)

Nodes belong to different components.

Result: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E log E + V log V + Q log V)	Sorting edges, preprocessing ancestors, logarithmic queries
Space	O(V log V)	Binary lifting tables and MST storage

Sorting edges dominates the MST construction phase. Binary lifting preprocessing requires storing ancestors for every power of two.

Each query only performs upward jumps in the tree, so it runs in logarithmic time.

Test Cases

# Provided example
obj = DistanceLimitedPathsExist(
    6,
    [[0,2,4],[0,3,2],[1,2,3],[2,3,1],[4,5,5]]
)

assert obj.query(2, 3, 2) == True   # direct edge with weight 1
assert obj.query(1, 3, 3) == False  # strict inequality failure
assert obj.query(2, 0, 3) == True   # multi edge valid path
assert obj.query(0, 5, 6) == False  # disconnected graph

# Simple chain
obj = DistanceLimitedPathsExist(
    4,
    [[0,1,1],[1,2,2],[2,3,3]]
)

assert obj.query(0, 3, 4) == True   # all edges below limit
assert obj.query(0, 3, 3) == False  # edge weight 3 not allowed

# Multiple edges between same nodes
obj = DistanceLimitedPathsExist(
    3,
    [[0,1,10],[0,1,2],[1,2,3]]
)

assert obj.query(0, 2, 4) == True   # smaller parallel edge used
assert obj.query(0, 2, 3) == False  # edge weight 3 invalid

# Fully disconnected graph
obj = DistanceLimitedPathsExist(
    5,
    []
)

assert obj.query(0, 1, 10) == False # no edges exist

# Single valid edge
obj = DistanceLimitedPathsExist(
    2,
    [[0,1,5]]
)

assert obj.query(0, 1, 6) == True   # valid threshold
assert obj.query(0, 1, 5) == False  # strict comparison

# Dense graph
obj = DistanceLimitedPathsExist(
    5,
    [
        [0,1,1],
        [0,2,2],
        [1,2,1],
        [1,3,3],
        [2,4,4],
        [3,4,2]
    ]
)

assert obj.query(0, 4, 5) == True   # path exists
assert obj.query(0, 4, 3) == False  # bottleneck too large

Test Case Summary

Test	Why
Provided example	Validates standard functionality
Simple chain	Tests path maximum logic
Multiple parallel edges	Ensures MST chooses smaller edge
Empty graph	Validates disconnected handling
Single edge	Tests strict inequality behavior
Dense graph	Verifies bottleneck path correctness

Edge Cases

Strictly Less Than Limit

One of the most common mistakes is using <= limit instead of < limit.

For example:

Edge weight = 5
Limit = 5

This edge is invalid because the problem requires strict inequality.

The implementation handles this correctly by checking:

maximum < limit

rather than allowing equality.

Disconnected Components

The graph may contain completely separate components. Queries between such nodes should immediately return false.

The implementation handles this efficiently using Union Find. Before performing any LCA logic, it checks whether both nodes belong to the same component.

This prevents invalid ancestor traversal and avoids unnecessary computation.

Multiple Edges Between the Same Nodes

The graph may contain several edges connecting identical endpoints with different weights.

A naive implementation might incorrectly use the larger edge. Kruskal's algorithm naturally avoids this issue because edges are processed in sorted order. The smallest useful edge is chosen first, and larger redundant edges are skipped if they create cycles.

This guarantees the MST preserves the optimal bottleneck structure.

Graph with No Edges

If edgeList is empty, every node forms its own component.

DFS preprocessing still works because each node becomes an isolated tree root. Queries correctly return false for all distinct node pairs.

The implementation safely handles this without special case logic.