LeetCode 3534 - Path Existence Queries in a Graph II

LeetCode Problem 3534

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Dynamic Programming, Greedy, Bit Manipulation, Graph Theory, Sorting

Solution

Problem Understanding

This problem asks us to compute the shortest path between nodes in an implicit undirected graph defined by a nums array and a maxDiff. Each node i corresponds to nums[i]. There is an edge between nodes i and j if the absolute difference of their values is at most maxDiff. The input also includes a list of queries, each asking for the minimum distance between two nodes, or -1 if no path exists.

The input constraints are large: n and the number of queries can each be up to 10^5. A naive approach that explicitly constructs the adjacency list and runs BFS for each query would be too slow, potentially O(n^2) just to form edges. Therefore, we must exploit the structure of the problem to avoid explicitly building the full graph.

Key observations include:

1. Nodes are effectively connected if their values are within maxDiff. This allows us to sort nodes by value and quickly identify contiguous ranges of nodes that form connected components.
2. Once connected components are identified, any query between nodes in the same component has a path; otherwise, no path exists.
3. Since edges are unweighted, the minimum distance between any two nodes in a fully connected component of consecutive nodes is 1 if they are directly adjacent by value, otherwise more depending on how far they are in the value ordering.

Edge cases to consider include:

• maxDiff = 0, meaning only nodes with the same value are connected.
• Queries asking the distance from a node to itself.
• Disconnected graphs, where some nodes have no edges at all.

The goal is to answer all queries efficiently, ideally using sorting + union-find (disjoint set union) to precompute connected components, and then handle queries in constant time per query.

Approaches

Brute Force

The brute-force approach would be:

1. Build the adjacency list explicitly: for each pair of nodes (i, j), check if |nums[i] - nums[j]| <= maxDiff and add an edge if true.
2. For each query, run BFS or DFS to find the shortest path between ui and vi.

This approach works for small inputs but has severe limitations:

• Building edges is O(n^2) in the worst case.
• BFS per query is O(n + m), where m is the number of edges, leading to up to O(n^2) per query.
• Total time complexity is far too high for n = 10^5.

Optimal Approach

The key insight is that nodes can be grouped into connected components based on value ranges. If we sort the nodes by nums[i], then all nodes within a contiguous segment where consecutive values differ by at most maxDiff belong to the same component.

Steps:

1. Sort nodes by nums[i].
2. Iterate over sorted nodes, unioning consecutive nodes whose difference is <= maxDiff.
3. For each query [ui, vi], check if ui and vi belong to the same component. If yes, distance is 1 (or 0 if they are the same node), else -1.

This transforms the problem from graph traversal to a union-find connected component problem, which can be solved efficiently in O(n log n) due to sorting and nearly O(1) per union/find with path compression.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2 + q * n)	O(n^2)	Explicitly build graph and run BFS per query
Optimal	O(n log n + q)	O(n)	Sort nodes + union-find to precompute connected components

Algorithm Walkthrough

1. Create an array of pairs (num, index) for all nodes.
2. Sort this array by num.
3. Initialize a union-find data structure for n nodes.
4. Iterate through sorted nodes. For each consecutive pair (prev, curr), if curr.num - prev.num <= maxDiff, union their indices.
5. For each query [ui, vi], check if ui and vi belong to the same component using union-find. If yes, return 0 if ui == vi, else 1. If not, return -1.

Why it works: Sorting ensures all nodes that could be connected are examined consecutively. Union-find ensures that any indirect connection through multiple nodes is also recognized. Queries then become constant-time lookups. This problem defines an undirected graph implicitly from an array of values rather than from an explicit edge list. Each node corresponds to an index in the array nums, and an edge exists between two nodes i and j if and only if the absolute difference between their values is within a threshold, meaning |nums[i] - nums[j]| <= maxDiff. Once this graph is defined, we are asked to answer multiple shortest path queries between pairs of nodes, returning the minimum number of edges required to travel from one node to another, or -1 if no path exists.

The key challenge is that the graph is not explicitly given, and it is also extremely dense in the worst case, potentially connecting many pairs of nodes. Additionally, both n and the number of queries can be as large as 100,000, which makes any per-query graph traversal like BFS or DFS infeasible.

The input consists of an integer n, an array nums of length n, a threshold maxDiff, and a list of queries. Each query asks for the shortest path distance between two nodes in the implicitly constructed graph.

The output is an array where each entry corresponds to the shortest path length for the corresponding query.

Important edge cases include situations where maxDiff = 0, which only allows edges between equal values, cases where the graph becomes fully connected when maxDiff is large, and cases where queries ask for self-distances, which should always return 0.

Approaches

Brute Force Approach

The most straightforward approach is to explicitly construct the graph by checking every pair of nodes and adding an edge if their values differ by at most maxDiff. This results in an adjacency list. Then, for each query, we run a BFS from the source node to compute the shortest path to the target node.

This approach is correct because BFS on an unweighted graph always yields the shortest path in terms of edge count. However, constructing the graph requires O(n²) comparisons, and running BFS per query can cost O(n + m), making it far too slow when both n and q are large.

Key Insight for Optimization

The crucial observation is that the graph depends only on the values in nums, not on arbitrary connectivity. If we sort nodes by their values, then nodes that can connect must lie within contiguous regions of the sorted array where consecutive differences are within maxDiff.

This transforms the problem into grouping nodes into connected components based on value adjacency after sorting. Once nodes are assigned to components, any two nodes are either unreachable or their shortest path depends on their relative order within the sorted structure.

We can further optimize by realizing that within a connected component, the shortest path between two nodes corresponds to stepping through adjacent elements in sorted order, since edges effectively form a “sliding window connectivity” structure.

This allows preprocessing of connectivity and answering queries in near O(1) or O(log n) depending on implementation.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force BFS per query	O(n² + q(n + m))	O(n + m)	Explicit graph construction, infeasible for constraints
Sorting + component grouping	O(n log n + q)	O(n)	Efficient preprocessing using sorted structure and grouping

Algorithm Walkthrough

The optimal solution relies on sorting indices by their corresponding values and then using this ordering to build connected components.

1. First, we pair each index with its value and sort these pairs by value. This allows us to reason about connectivity in a linear order where differences between adjacent elements determine possible edges. Sorting is necessary because the edge condition depends on absolute differences, which becomes locally checkable after ordering.
2. We then scan the sorted array and group nodes into connected components. We maintain a current component start, and whenever the difference between consecutive values exceeds maxDiff, we close the current component and start a new one. This works because if two adjacent values differ too much, no chain can bridge across that gap.
3. For each node, we record its component identifier. This allows us to later determine whether two nodes can reach each other at all in constant time per query.
4. For answering queries, we first check whether both nodes belong to the same component. If not, we immediately return -1 because there is no path between disconnected components.
5. If they are in the same component, we compute their positions within the sorted order and return the absolute difference of their positions. This works because within a connected component, the shortest path corresponds to stepping through adjacent nodes in sorted order, since edges exist between sufficiently close values and the component is contiguous.
6. We repeat this process for all queries.

Why it works

The correctness comes from the fact that sorting transforms the arbitrary graph into a structure where connectivity is equivalent to being within a contiguous segment separated by gaps greater than maxDiff. Within each segment, adjacency behaves like a chain, and BFS shortest paths reduce to linear distance along that chain.

Python Solution

from typing import List

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, x: int, y: int):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        else:
            self.parent[py] = px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]:
        nodes = sorted([(num, idx) for idx, num in enumerate(nums)])
        uf = UnionFind(n)
        for i in range(1, n):
            if nodes[i][0] - nodes[i - 1][0] <= maxDiff:
                uf.union(nodes[i][1], nodes[i - 1][1])
        result = []
        for u, v in queries:
            if u == v:
                result.append(0)
            elif uf.find(u) == uf.find(v):
                result.append(1)
            else:
                result.append(-1)
        return result

Explanation: We first sort the nodes by value, then iterate through them to union nodes that are within maxDiff. Finally, we answer queries by checking component membership. Self-queries return 0. class Solution: def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]: indexed = [(nums[i], i) for i in range(n)] indexed.sort()

    component = [-1] * n
    pos_in_sorted = [0] * n

    comp_id = 0
    start = 0

    for i in range(n):
        val, idx = indexed[i]
        pos_in_sorted[idx] = i

        if i == start:
            component[idx] = comp_id
        else:
            prev_val = indexed[i - 1][0]
            if val - prev_val <= maxDiff:
                component[idx] = comp_id
            else:
                comp_id += 1
                start = i
                component[idx] = comp_id

    res = []
    for u, v in queries:
        if component[u] != component[v]:
            res.append(-1)
        else:
            res.append(abs(pos_in_sorted[u] - pos_in_sorted[v]))
    return res

### Implementation Explanation

We first sort `(value, index)` pairs so that nodes are ordered by `nums`. We then iterate through this sorted list and assign component IDs whenever we detect a gap larger than `maxDiff`. Each index receives both a component label and its position in the sorted array.

For queries, we simply compare component IDs. If they differ, no path exists. Otherwise, we compute the distance using the difference in sorted positions, which corresponds to the shortest path length in this chain-like structure.

## Go Solution

```go
package main

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, 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(x, y int) {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return
	}
	if uf.rank[px] < uf.rank[py] {
		uf.parent[px] = py
	} else {
		uf.parent[py] = px
		if uf.rank[px] == uf.rank[py] {
			uf.rank[px]++
		}
	}
}

func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) []int {
	type node struct {
		val int
		idx int
	}
	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i] = node{nums[i], i}
	}
	// sort nodes by value
	sort.Slice(nodes, func(i, j int) bool { return nodes[i].val < nodes[j].val })
	uf := NewUnionFind(n)
	for i := 1; i < n; i++ {
		if nodes[i].val - nodes[i-1].val <= maxDiff {
			uf.Union(nodes[i].idx, nodes[i-1].idx)
		}
	}
	ans := make([]int, len(queries))
	for i, q := range queries {
		u, v := q[0], q[1]
		if u == v {
			ans[i] = 0
		} else if uf.Find(u) == uf.Find(v) {
			ans[i] = 1
		} else {
			ans[i] = -1
		}
	}
import (
	"sort"
)

func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) []int {
	type pair struct {
		val int
		idx int
	}

	arr := make([]pair, n)
	for i := 0; i < n; i++ {
		arr[i] = pair{nums[i], i}
	}

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

	component := make([]int, n)
	pos := make([]int, n)

	compID := 0
	start := 0

	for i := 0; i < n; i++ {
		pos[arr[i].idx] = i

		if i == start {
			component[arr[i].idx] = compID
		} else {
			if arr[i].val-arr[i-1].val <= maxDiff {
				component[arr[i].idx] = compID
			} else {
				compID++
				start = i
				component[arr[i].idx] = compID
			}
		}
	}

	ans := make([]int, len(queries))
	for i, q := range queries {
		u, v := q[0], q[1]
		if component[u] != component[v] {
			ans[i] = -1
		} else {
			diff := pos[u] - pos[v]
			if diff < 0 {
				diff = -diff
			}
			ans[i] = diff
		}
	}

	return ans
}

Explanation: The Go solution mirrors Python closely. Sorting is done with sort.Slice, union-find uses slices for parent and rank, and queries are answered similarly. Differences are mainly language-specific syntax and types.

Go-specific notes

The Go implementation mirrors the Python logic but uses a struct slice and sort.Slice. Integer arithmetic is safe because values are within constraints. We explicitly compute absolute differences since Go lacks a built-in abs for integers. Slices are used for all arrays to maintain efficiency and simplicity.

Worked Examples

Example 1

Input: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]

Sorted nodes: [(1,0),(2,4),(3,2),(4,3),(8,1)]

Union operations:

• 1-2: union(0,4)
• 2-3: union(4,2)
• 3-4: union(2,3)
• 4-8: skipped

Query 0-3: same component → 1

Query 2-4: same component → 1

Output: [1,1]

Example 2

Input: `nums = [5,3,1,9,10], max Input:

nums = [1, 8, 3, 4, 2], maxDiff = 3

Sorted:

(1,0), (2,4), (3,2), (4,3), (8,1)

Component formation:

Index	Value	Diff with prev	Component
0	1	-	0
4	2	1	0
2	3	1	0
3	4	1	0
1	8	4	1

Thus:

• Component 0 contains nodes 0,4,2,3
• Component 1 contains node 1

Queries:

• (0,3): same component → distance = |pos(0)-pos(3)| = 0 to 3 in sorted chain → 1
• (2,4): same component → distance = 1

Example 2

Sorted:

[1,3,5,9,10]

Components:

• [0,1,2] form one component
• [3,4] form another

Query analysis:

• (0,2): within component → distance 2
• (2,3): different components → -1

Example 3

No adjacent values satisfy maxDiff = 1, so every node is isolated.

All queries between distinct nodes return -1, self-query returns 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + q)	Sorting dominates, queries are O(1) each
Space	O(n)	Arrays for sorting, component mapping, and positions

Sorting dominates runtime. Once sorted, single pass grouping and constant-time query resolution ensures scalability.

Test Cases

assert Solution().pathExistenceQueries(5, [1,8,3,4,2], 3, [[0,3],[2,4]]) == [1,1]  # example 1
assert Solution().pathExistenceQueries(5, [5,3,1,9,10], 2, [[0,1],[0,2],[2,3],[4,3]]) == [1,2,-1,1]  # example 2
assert Solution().pathExistenceQueries(3, [3,6,1], 1, [[0,0],[0,1],[1,2]]) == [0,-1,-1]  # example 3

assert Solution().pathExistenceQueries(1, [10], 5, [[0,0]]) == [0]  # single node
assert Solution().pathExistenceQueries(4, [1,2,3,100], 1, [[0,2],[0,3]]) == [2,-1]  # mixed connectivity
assert Solution().pathExistenceQueries(6, [1,2,3,4,5,6], 10, [[0,5]]) == [5]  # fully connected chain
assert Solution().pathExistenceQueries(5, [1,1,1,1,1], 0, [[0,4]]) == [4]  # identical values

Test	Why
single node	verifies self-distance base case
mixed connectivity	tests disconnected components
fully connected chain	validates longest-path within component
identical values	ensures maxDiff=0 still connects correctly

Edge Cases

One important edge case is when n = 1. In this case, there are no edges and any query must return 0 if it is a self-query. The algorithm handles this naturally because the component assignment assigns a single node component and the position difference is zero.

Another edge case occurs when maxDiff = 0. Here, only nodes with identical values can be connected. The sorting-based grouping correctly isolates nodes unless consecutive values are equal, ensuring correctness even with duplicate-heavy inputs.

A third edge case is when the array is already sorted and maxDiff is very large. In this scenario, the entire graph becomes a single connected component, and the shortest path reduces to simple index distance in the sorted order. The algorithm correctly merges everything into one component and returns accurate distances in linear structure form.