LeetCode Problem 3532

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Union-Find, Graph Theory

Solution

Path Existence Queries in a Graph I

Problem Understanding

This problem defines an undirected graph implicitly through a sorted array nums.

Each index in nums represents a graph node. Two nodes i and j are connected by an edge whenever:

$$|nums[i] - nums[j]| \le maxDiff$$

We are then given many connectivity queries. For each query [u, v], we must determine whether there exists a path from node u to node v.

A path does not need to be a direct edge. It may pass through intermediate nodes. Therefore, the task is fundamentally a graph connectivity problem.

The most important observation is that the graph is not provided explicitly. With up to 100,000 nodes, constructing every possible edge would be impossible because there could be billions of potential pairs.

The constraints are large:

• n ≤ 100,000
• queries.length ≤ 100,000
• nums is already sorted in non-decreasing order

These constraints immediately rule out any solution that examines all pairs of nodes or performs a graph traversal for every query.

Several edge cases are worth noting:

• A query may ask whether a node can reach itself. The answer is always true.
• maxDiff may be 0, meaning only equal values can be directly connected.
• Multiple equal values may appear because nums is only non-decreasing, not strictly increasing.
• The graph may consist of many disconnected components.
• A path may exist even when two queried nodes are not directly connected, because intermediate nodes can bridge the gap.

The key challenge is identifying connected components efficiently without explicitly building the entire graph.

Approaches

Brute Force

A straightforward approach would be to build the graph explicitly.

For every pair of nodes (i, j), we check whether:

$$|nums[i] - nums[j]| \le maxDiff$$

If so, we add an edge.

After constructing the graph, we could answer each query using either BFS or DFS to determine whether the two nodes belong to the same connected component.

This approach is correct because it directly follows the graph definition. However, it is far too slow.

There are O(n²) possible node pairs. With n = 100,000, this becomes completely infeasible.

Key Insight

The crucial observation comes from the fact that nums is sorted.

Suppose:

nums[i+1] - nums[i] <= maxDiff

Then nodes i and i+1 have a direct edge.

Now suppose:

nums[i+1] - nums[i] > maxDiff

Because the array is sorted, every value to the right of i+1 is even larger. Therefore no node on the left side can connect to any node on the right side through a chain of valid edges.

This means every gap larger than maxDiff creates a permanent separation between connected components.

As a result, we do not need to examine all pairs.

We only need to scan adjacent elements:

• If adjacent values differ by at most maxDiff, merge their indices.
• Otherwise, start a new component.

A Union-Find (Disjoint Set Union, DSU) structure is ideal for maintaining these connected components.

After all adjacent merges are performed, two nodes have a path between them if and only if they belong to the same DSU set.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² + q·(n+m))	O(n²)	Explicitly builds graph and runs traversals
Optimal	O(n α(n) + q α(n))	O(n)	Union adjacent nodes only, answer with DSU

Here q is the number of queries and α(n) is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

Optimal Algorithm

1. Create a Union-Find data structure with n nodes.
2. Scan the array from left to right.
3. For every adjacent pair (i-1, i), compute:

nums[i] - nums[i-1]

4. If this difference is at most maxDiff, union the two indices.

This is sufficient because any larger connected region can be formed by chaining adjacent valid connections. 5. If the difference is greater than maxDiff, do nothing.

Such a gap separates two connected components permanently. 6. After processing all adjacent pairs, every connected component has been identified. 7. For each query [u, v], check whether:

find(u) == find(v)

8. If the roots are equal, append true.
9. Otherwise, append false.
10. Return the resulting boolean array.

Why it works

Because nums is sorted, every path between indices must cross each adjacent gap lying between them.

If an adjacent gap exceeds maxDiff, no edge can cross that gap, and therefore no path can cross it either.

Conversely, if every adjacent gap inside a segment is at most maxDiff, then consecutive nodes are directly connected, creating a chain that connects the entire segment.

Thus connected components are exactly the maximal contiguous index ranges whose adjacent differences are all at most maxDiff. Unioning only adjacent valid pairs therefore reconstructs the complete connectivity structure of the graph.

Problem Understanding

This problem gives a graph defined implicitly rather than explicitly. You are given n nodes labeled from 0 to n - 1, and an array nums that is already sorted in non-decreasing order. Two nodes i and j are connected by an undirected edge if and only if the absolute difference between their values in nums is at most maxDiff.

The key task is not to construct all edges explicitly, but to answer multiple queries efficiently. Each query asks whether there exists any path between two nodes ui and vi in this graph. Since paths can go through intermediate nodes, we are effectively being asked whether the two nodes lie in the same connected component.

The constraints make it clear that both n and the number of queries can be up to 10^5, so any solution that explores the graph per query would be too slow. This strongly suggests that we must preprocess the graph structure once and then answer queries in near O(1) time.

A crucial observation comes from the fact that nums is sorted. This guarantees that connectivity is governed by local adjacency: if two far-apart indices are connected, then there must be a chain of adjacent indices connecting them, and those adjacent differences must all satisfy the maxDiff constraint.

Edge cases include when maxDiff = 0, where only equal values connect, or when all differences are small enough that the entire graph becomes a single connected component. Another important case is when no adjacent pair satisfies the condition, resulting in all nodes being isolated.

Approaches

The brute-force approach builds the graph explicitly and then runs a search for each query. The optimal approach recognizes that the graph is a union of contiguous segments formed by adjacent indices where nums[i+1] - nums[i] <= maxDiff, and thus connectivity reduces to checking whether two nodes belong to the same segment.

Key Insight

Because nums is sorted, any valid path must move through increasing indices, and edges only “bridge” adjacent elements that satisfy the difference constraint. Therefore, instead of considering all pairs (i, j), it is sufficient to connect only adjacent indices and merge them into components using a Union-Find structure or a linear scan labeling approach.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q · (n + m))	O(n + m)	Build graph and BFS/DFS per query
Optimal (Union-Find / Component Scan)	O(n + q α(n))	O(n)	Merge adjacent valid pairs and answer via connectivity check

Algorithm Walkthrough

We use a Union-Find (Disjoint Set Union) structure to maintain connected components efficiently.

1. We initialize a Union-Find structure where each node starts in its own component. This represents the initial state where no edges are assumed.
2. We iterate through the array nums from index 0 to n - 2. For each adjacent pair (i, i+1), we check whether nums[i+1] - nums[i] <= maxDiff.
3. If the condition holds, we union the two indices i and i+1. This step is sufficient because connectivity between non-adjacent nodes is always transitive through adjacent valid links in a sorted array.
4. After preprocessing, each node belongs to a final connected component represented by its root parent in the Union-Find structure.
5. For each query [ui, vi], we simply check whether find(ui) == find(vi). If they share the same root, a path exists; otherwise, it does not.

Why it works

The correctness relies on the invariant that any valid path in this graph must correspond to a sequence of adjacent indices where each step satisfies the maxDiff constraint. Because the array is sorted, any edge that could exist between non-adjacent nodes is already implied by a chain of adjacent edges. Thus, unioning only adjacent valid pairs fully captures all connectivity information.

Python Solution

from typing import List

class Solution:
    def pathExistenceQueries(
        self,
        n: int,
        nums: List[int],
        maxDiff: int,
        queries: List[List[int]]
    ) -> List[bool]:

    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        parent = list(range(n))
        rank = [0] * n

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

        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

        for i in range(1, n):
            if nums[i] - nums[i - 1] <= maxDiff:
                union(i, i - 1)

        answer = []

        for u, v in queries:
            answer.append(find(u) == find(v))

        return answer

The implementation begins by creating a standard Union-Find structure with path compression and union by rank.

The main preprocessing step scans adjacent elements of the sorted array. Whenever the difference between neighboring values is at most maxDiff, the corresponding indices are merged into the same DSU component.

After this preprocessing, each connected component of the graph corresponds to one DSU set.

Each query is then answered independently by comparing the representatives of the two queried nodes. If the representatives are identical, a path exists; otherwise it does not.

Because DSU operations are nearly constant time, the solution remains efficient even at the maximum input size. while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x

    def union(a: int, b: int) -> None:
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1

    for i in range(n - 1):
        if nums[i + 1] - nums[i] <= maxDiff:
            union(i, i + 1)

    result = []
    for u, v in queries:
        result.append(find(u) == find(v))

    return result

The implementation first constructs the Union-Find structure. The `find` function uses path compression to flatten the structure for efficiency. The `union` function merges two components using union by rank to keep trees shallow.

We then iterate through adjacent pairs and union indices that satisfy the constraint. Finally, each query is answered in near constant time by comparing roots.

## Go Solution

```go
package main

func pathExistenceQueries(n int, nums []int, maxDiff 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(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(a, 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]++
		}
	}

	for i := 1; i < n; i++ {
		if nums[i]-nums[i-1] <= maxDiff {
			union(i, i-1)
		ra, rb := find(a), find(b)
		if ra == rb {
			return
		}
		if rank[ra] < rank[rb] {
			ra, rb = rb, ra
		}
		parent[rb] = ra
		if rank[ra] == rank[rb] {
			rank[ra]++
		}
	}

	for i := 0; i < n-1; i++ {
		if nums[i+1]-nums[i] <= maxDiff {
			union(i, i+1)
		}
	}

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

	for i, q := range queries {
		u, v := q[0], q[1]
		ans[i] = find(u) == find(v)
	for i, q := range queries {
		ans[i] = find(q[0]) == find(q[1])
	}

	return ans
}

The Go implementation mirrors the Python solution closely. Slices are used for the parent and rank arrays. Path compression is implemented recursively through a closure. Since all values fit comfortably within standard integer limits, no special overflow handling is required. In Go, we use slices for parent and rank. The recursive find function performs path compression similarly to Python. One key difference is that Go requires explicit closure definitions for recursive functions, and we must ensure initialization of the parent array before unions begin.

Worked Examples

Example 1

Input

n = 2
nums = [1, 3]
maxDiff = 1
queries = [[0,0], [0,1]]

Building Components

i	Adjacent Pair	Difference	Union?
1	(0,1)	2	No

DSU state:

| Node | Root | Input: n = 2, nums = [1, 3], maxDiff = 1

We first check adjacency:

• nums[1] - nums[0] = 2, which is greater than 1, so no union occurs.

Union-Find state:

Node	Parent
0	0
1	1

Processing Queries

Query	Same Root?	Result
[0,0]	Yes	true
[0,1]	No	false

Output:

[true, false]

Example 2

Input

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

Building Components

i	Adjacent Pair	Difference	Action
1	(0,1)	3	No union
2	(1,2)	1	Union
3	(2,3)	2	Union

After unions:

Component A: {0}
Component B: {1,2,3}

DSU Roots

Node	Root
0	0
1	1
2	1
3	1

Query Evaluation

Query	Roots	Result
[0,1]	0,1	false
[0,2]	0,1	false
[1,3]	1,1	true
[2,3]	1,1	true

Output:

[false, false, true, true]

Queries:

• [0,0]: same root → true
• [0,1]: different roots → false

Output: [true, false]

Example 2

Input: nums = [2, 5, 6, 8], maxDiff = 2

Adjacency checks:

1. 5 - 2 = 3 → no union
2. 6 - 5 = 1 → union(1, 2)
3. 8 - 6 = 2 → union(2, 3)

Union-Find evolves:

• After union(1,2): {1,2}
• After union(2,3): {1,2,3}

Final components:

Node	Parent Set
0	{0}
1	{1,2,3}
2	{1,2,3}
3	{1,2,3}

Queries:

• [0,1]: different components → false
• [0,2]: different components → false
• [1,3]: same component → true
• [2,3]: same component → true

Output: [false, false, true, true]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n α(n) + q α(n))	DSU unions and finds are nearly constant time
Space	O(n)	Parent and rank arrays

The preprocessing phase examines only n - 1 adjacent differences. Each valid adjacent pair causes one union operation. Query answering requires two find operations per query. Because Union-Find with path compression and union by rank has amortized complexity α(n), which is effectively constant, the overall runtime is linear in the input size. | Time | O(n + q α(n)) | One pass unions plus near-constant query checks | | Space | O(n) | Parent and rank arrays for Union-Find |

The time complexity is dominated by a single traversal of the array plus almost constant-time Union-Find operations due to path compression and union by rank. Each query is answered in effectively O(1) amortized time.

Test Cases

from typing import List

s = Solution()

assert s.pathExistenceQueries(
    2,
    [1, 3],
    1,
    [[0, 0], [0, 1]]
) == [True, False]  # example 1

assert s.pathExistenceQueries(
    4,
    [2, 5, 6, 8],
    2,
    [[0, 1], [0, 2], [1, 3], [2, 3]]
) == [False, False, True, True]  # example 2

assert s.pathExistenceQueries(
    1,
    [5],
    0,
    [[0, 0]]
) == [True]  # single node

assert s.pathExistenceQueries(
    5,
    [1, 2, 3, 4, 5],
    10,
    [[0, 4], [1, 3]]
) == [True, True]  # fully connected graph

assert s.pathExistenceQueries(
    5,
    [1, 10, 20, 30, 40],
    0,
    [[0, 1], [2, 2], [3, 4]]
) == [False, True, False]  # isolated nodes

assert s.pathExistenceQueries(
    5,
    [7, 7, 7, 7, 7],
    0,
    [[0, 4], [1, 3]]
) == [True, True]  # duplicate values

assert s.pathExistenceQueries(
    6,
    [1, 2, 10, 11, 20, 21],
    1,
    [[0, 1], [0, 3], [2, 3], [4, 5]]
) == [True, False, True, True]  # multiple components

assert s.pathExistenceQueries(
    4,
    [1, 2, 4, 5],
    1,
    [[0, 1], [1, 2], [2, 3], [0, 3]]
) == [True, False, True, False]  # component boundary gap

Test Summary

Test	Why
Example 1	Verifies disconnected nodes
Example 2	Verifies path through intermediate nodes
Single node	Smallest valid input
Fully connected graph	Every node belongs to one component
Isolated nodes	No unions occur
Duplicate values	Tests maxDiff = 0 with equal numbers
Multiple components	Verifies several disconnected groups
Boundary gap	Ensures large gaps split components correctly

Edge Cases

Querying the Same Node

A query such as [u, u] should always return true because every node has a trivial path to itself. A buggy implementation might accidentally perform unnecessary graph logic and mishandle this case. In the DSU solution, both endpoints have the same representative automatically, so the answer is correctly true.

maxDiff = 0

When maxDiff is zero, only equal values may be connected directly. Since the array can contain duplicates, some nodes may still form connected components. The adjacent-difference check naturally handles this because only adjacent equal values satisfy:

nums[i] - nums[i-1] <= 0

All duplicate runs become connected while distinct values remain separated.

Large Gaps Splitting Components

Consider:

nums = [1, 2, 3, 100, 101]
maxDiff = 2

The gap between 3 and 100 is much larger than maxDiff. Because the array is sorted, no path can cross this boundary. The algorithm correctly leaves the two sides in separate DSU components, ensuring all connectivity queries across the gap return false.

All Nodes Connected Through a Chain

Even if the first and last nodes differ by much more than maxDiff, they may still be connected through intermediate nodes. For example:

nums = [1, 3, 5]
maxDiff = 2

Node 0 connects to node 1, and node 1 connects to node 2, creating a path from node 0 to node 2. The DSU approach captures this transitive connectivity through repeated unions, producing the correct result. def test(): sol = Solution()

assert sol.pathExistenceQueries(2, [1, 3], 1, [[0, 0], [0, 1]]) == [True, False]

assert sol.pathExistenceQueries(4, [2, 5, 6, 8], 2,
                               [[0, 1], [0, 2], [1, 3], [2, 3]]) == \
       [False, False, True, True]

assert sol.pathExistenceQueries(1, [10], 0, [[0, 0]]) == [True]

assert sol.pathExistenceQueries(5, [1, 2, 3, 4, 5], 10,
                               [[0, 4], [1, 3]]) == [True, True]

assert sol.pathExistenceQueries(5, [1, 10, 20, 30, 40], 0,
                               [[0, 1], [1, 2]]) == [False, False]

assert sol.pathExistenceQueries(6, [1, 2, 4, 7, 11, 12], 2,
                               [[0, 1], [1, 2], [3, 5], [0, 5]]) == \
       [True, False, True, False]

test()

| Test | Why |
| --- | --- |
| single node | trivial connectivity always true |
| sample cases | validates correctness on standard graph |
| full connectivity | checks all nodes connected when maxDiff large |
| no connectivity | ensures isolated nodes handled correctly |
| mixed segments | tests multiple components |

## Edge Cases

One important edge case is when `n = 1`. In this scenario, there are no edges and every query `[0, 0]` must return true. The Union-Find structure naturally handles this because the single node is its own parent.

Another edge case occurs when `maxDiff = 0`. Here, only identical adjacent values can be connected. This means components form groups of equal values, and the algorithm correctly unions only identical adjacent elements.

A third edge case is when the entire array is strictly increasing but all adjacent differences are within `maxDiff`. In this case, the entire graph becomes a single connected component. The algorithm handles this by repeatedly unioning adjacent pairs, resulting in one root for all nodes.