# Path Existence Queries in a Graph I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-existence-queries-in-a-graph-i)
Canonical: https://scaleengineer.com/dsa/problems/path-existence-queries-in-a-graph-i
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Graph
---
## Problem
You are given an integer `n` representing the number of nodes in a graph, labeled from 0 to `n - 1`.

You are also given an integer array `nums` of length `n` sorted in **non-decreasing** order, and an integer `maxDiff`.

An **undirected** edge exists between nodes `i` and `j` if the **absolute** difference between `nums[i]` and `nums[j]` is **at most** `maxDiff` (i.e., `|nums[i] - nums[j]| <= maxDiff`).

You are also given a 2D integer array `queries`. For each `queries[i] = [ui, vi]`, determine whether there exists a path between nodes `ui` and `vi`.

Return a boolean array `answer`, where `answer[i]` is `true` if there exists a path between `ui` and `vi` in the `ith` query and `false` otherwise.

**Example 1:**

**Input:** n = 2, nums = \[1,3\], maxDiff = 1, queries = \[\[0,0\],\[0,1\]\]

**Output:** \[true,false\]

**Explanation:**

* Query `[0,0]`: Node 0 has a trivial path to itself.
* Query `[0,1]`: There is no edge between Node 0 and Node 1 because `|nums[0] - nums[1]| = |1 - 3| = 2`, which is greater than `maxDiff`.
* Thus, the final answer after processing all the queries is `[true, false]`.

**Example 2:**

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

**Output:** \[false,false,true,true\]

**Explanation:**

The resulting graph is:

![](https://assets.glich.co/dsa/path-existence-queries-in-a-graph-i/image0.png)

* Query `[0,1]`: There is no edge between Node 0 and Node 1 because `|nums[0] - nums[1]| = |2 - 5| = 3`, which is greater than `maxDiff`.
* Query `[0,2]`: There is no edge between Node 0 and Node 2 because `|nums[0] - nums[2]| = |2 - 6| = 4`, which is greater than `maxDiff`.
* Query `[1,3]`: There is a path between Node 1 and Node 3 through Node 2 since `|nums[1] - nums[2]| = |5 - 6| = 1` and `|nums[2] - nums[3]| = |6 - 8| = 2`, both of which are within `maxDiff`.
* Query `[2,3]`: There is an edge between Node 2 and Node 3 because `|nums[2] - nums[3]| = |6 - 8| = 2`, which is equal to `maxDiff`.
* Thus, the final answer after processing all the queries is `[false, false, true, true]`.

**Constraints:**

* `1 <= n == nums.length <= 105`
* `0 <= nums[i] <= 105`
* `nums` is sorted in **non-decreasing** order.
* `0 <= maxDiff <= 105`
* `1 <= queries.length <= 105`
* `queries[i] == [ui, vi]`
* `0 <= ui, vi < n`

# Approaches
## Brute-force with Per-Query Graph Traversal
This approach tackles each query independently. For every query `[u, v]`, it first constructs the entire graph based on the given conditions: an edge exists between nodes `i` and `j` if `|nums[i] - nums[j]| <= maxDiff`. After building the graph, it performs a graph traversal, such as Breadth-First Search (BFS) or Depth-First Search (DFS), starting from node `u` to determine if node `v` is reachable. This process is repeated for all queries.
**Time:** `O(Q * n^2)`. For each of the `Q` queries, we build a graph which takes `O(n^2)` time to check all pairs of nodes. The subsequent BFS/DFS takes `O(n + E)`, where `E` can be up to `O(n^2)`. Thus, the total time is dominated by `O(Q * n^2)`. · **Space:** `O(n^2)`. The adjacency list can store up to `O(n^2)` edges in a dense graph.
**Pros:** Conceptually simple and easy to implement.
**Cons:** Highly inefficient due to redundant graph construction for each query.; Will result in a "Time Limit Exceeded" error for the given constraints.
### Explanation
The algorithm for this approach is as follows:
1. Initialize a boolean array `answer` to store the results for each query.
2. For each query `[u, v]` in the `queries` array:
    a. Create an adjacency list to represent the graph.
    b. Iterate through all unique pairs of nodes `(i, j)`.
    c. If `|nums[i] - nums[j]| <= maxDiff`, add an undirected edge between `i` and `j` in the adjacency list.
    d. Use BFS or DFS, starting from `u`, to traverse the graph. Keep track of visited nodes.
    e. If `v` is visited during the traversal, a path exists. Set the corresponding entry in `answer` to `true`. Otherwise, set it to `false`.
3. Return the `answer` array.

Here is a code snippet implementing this approach using BFS:
```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean[] pathExists(int n, int[] nums, int maxDiff, int[][] queries) {
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            
            if (u == v) {
                answer[i] = true;
                continue;
            }

            List<List<Integer>> adj = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                adj.add(new ArrayList<>());
            }

            for (int j = 0; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (Math.abs(nums[j] - nums[k]) <= maxDiff) {
                        adj.get(j).add(k);
                        adj.get(k).add(j);
                    }
                }
            }
            
            answer[i] = hasPath(n, adj, u, v);
        }
        return answer;
    }

    private boolean hasPath(int n, List<List<Integer>> adj, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == end) {
                return true;
            }
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- For each query `[u, v]`:
- Build an adjacency list for the graph by checking all pairs of nodes `(i, j)`.
- If `|nums[i] - nums[j]| <= maxDiff`, add an edge `(i, j)`.
- Perform a graph traversal (BFS/DFS) from `u`.
- If `v` is reached, a path exists.

## Pre-computation using Union-Find on Full Graph
To avoid re-computation, we can process the graph's connectivity information once. This approach involves building all the edges of the graph upfront and using a Disjoint Set Union (DSU) data structure to group nodes into connected components. After this one-time setup, each query `[u, v]` can be answered efficiently by checking if `u` and `v` belong to the same set.
**Time:** `O(n^2 * α(n) + Q * α(n))`, where `α(n)` is the very slow-growing inverse Ackermann function. The `O(n^2)` factor for checking all pairs of nodes makes this approach too slow for the given constraints. · **Space:** `O(n)` to store the parent array for the DSU data structure.
**Pros:** Queries are answered very quickly (nearly constant time) after the initial setup.
**Cons:** The initial setup of the DSU structure is computationally expensive due to the O(n^2) complexity.
### Explanation
The core idea is to represent connected components as sets in a DSU structure. We iterate through all possible edges and unite the sets of the connected nodes.
1. Initialize a DSU data structure with `n` nodes, each in its own component.
2. Iterate through all unique pairs of nodes `(i, j)`.
3. If `|nums[i] - nums[j]| <= maxDiff`, perform a `union` operation on nodes `i` and `j`.
4. After processing all pairs, the DSU structure will represent all the connected components of the graph.
5. For each query `[u, v]`, use the `find` operation to check if `u` and `v` have the same representative (root). If they do, a path exists.

Here is a code snippet for this approach:
```java
class Solution {
    class DSU {
        private int[] parent;
        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) parent[rootI] = rootJ;
        }
    }

    public boolean[] pathExists(int n, int[] nums, int maxDiff, int[][] queries) {
        DSU dsu = new DSU(n);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[i] - nums[j]) <= maxDiff) {
                    dsu.union(i, j);
                }
            }
        }
        
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            answer[i] = (dsu.find(u) == dsu.find(v));
        }
        
        return answer;
    }
}
```
### Algorithm
- Initialize a DSU structure for `n` nodes.
- Iterate through all pairs of nodes `(i, j)`.
- If `|nums[i] - nums[j]| <= maxDiff`, call `union(i, j)`.
- For each query `[u, v]`, check if `find(u) == find(v)`.

## Optimized Union-Find leveraging Sorted `nums`
This is the most efficient approach, which hinges on a key observation related to the `nums` array being sorted. The condition for an edge between `i` and `j` (`i < j`) is `nums[j] - nums[i] <= maxDiff`. If this holds, then for any intermediate index `k` (`i <= k < j`), the difference `nums[k+1] - nums[k]` is also less than or equal to `maxDiff`. This implies that if an edge exists between `i` and `j`, there must be a path between them formed by connecting adjacent indices `k` and `k+1`. Therefore, we only need to consider connecting adjacent nodes `i` and `i+1` if `nums[i+1] - nums[i] <= maxDiff`. This drastically reduces the number of pairs to check from `O(n^2)` to `O(n)`.
**Time:** `O(n * α(n) + Q * α(n))`. The DSU initialization takes `O(n)`. The loop for unions runs `n-1` times, with each union taking `O(α(n))`. Processing `Q` queries takes `O(Q * α(n))`. This is highly efficient. · **Space:** `O(n)` for the DSU data structure.
**Pros:** Optimal time and space complexity.; Effectively uses the sorted property of the input array to simplify the problem.
**Cons:** The correctness relies on a non-trivial insight about the graph's connectivity property which might not be immediately obvious.
### Explanation
The algorithm simplifies to building connected components based only on adjacent nodes in the sorted `nums` array.
1. Initialize a DSU data structure with `n` nodes.
2. Iterate through the `nums` array from `i = 0` to `n-2`.
3. For each `i`, if `nums[i+1] - nums[i] <= maxDiff`, perform a `union` operation on nodes `i` and `i+1`.
4. This single pass is sufficient to capture all connectivity information.
5. Process each query `[u, v]` by checking if `find(u) == find(v)`.

The implementation is as follows:
```java
class Solution {
    class DSU {
        private int[] parent;
        private int[] rank;

        public DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by rank
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    }

    public boolean[] pathExists(int n, int[] nums, int maxDiff, int[][] queries) {
        DSU dsu = new DSU(n);
        
        for (int i = 0; i < n - 1; i++) {
            if (nums[i+1] - nums[i] <= maxDiff) {
                dsu.union(i, i + 1);
            }
        }
        
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            answer[i] = (dsu.find(u) == dsu.find(v));
        }
        
        return answer;
    }
}
```
### Algorithm
- Initialize a DSU structure for `n` nodes.
- Iterate from `i = 0` to `n-2`.
- If `nums[i+1] - nums[i] <= maxDiff`, call `union(i, i+1)`.
- For each query `[u, v]`, check if `find(u) == find(v)`.

# Solutions
### Java

```java
class Solution {
public
  boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff,
                                 int[][] queries) {
    int[] g = new int[n];
    int cnt = 0;
    for (int i = 1; i < n; ++i) {
      if (nums[i] - nums[i - 1] > maxDiff) {
        cnt++;
      }
      g[i] = cnt;
    }
    int m = queries.length;
    boolean[] ans = new boolean[m];
    for (int i = 0; i < m; ++i) {
      int u = queries[i][0];
      int v = queries[i][1];
      ans[i] = g[u] == g[v];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> pathExistenceQueries(int n, vector<int> &nums, int maxDiff,
                                    vector<vector<int>> &queries) {
    vector<int> g(n);
    int cnt = 0;
    for (int i = 1; i < n; ++i) {
      if (nums[i] - nums[i - 1] > maxDiff) {
        ++cnt;
      }
      g[i] = cnt;
    }
    vector<bool> ans;
    for (const auto &q : queries) {
      int u = q[0], v = q[1];
      ans.push_back(g[u] == g[v]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]: g = [0] * n cnt = 0 for i in range(1, n): if nums[i] - nums[i - 1] > maxDiff: cnt += 1 g[i] = cnt return [g[u] == g[v] for u, v in queries]

```