Path Existence Queries in a Graph I
MedPrompt
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 thanmaxDiff. - 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:
- Query
[0,1]: There is no edge between Node 0 and Node 1 because|nums[0] - nums[1]| = |2 - 5| = 3, which is greater thanmaxDiff. - Query
[0,2]: There is no edge between Node 0 and Node 2 because|nums[0] - nums[2]| = |2 - 6| = 4, which is greater thanmaxDiff. - Query
[1,3]: There is a path between Node 1 and Node 3 through Node 2 since|nums[1] - nums[2]| = |5 - 6| = 1and|nums[2] - nums[3]| = |6 - 8| = 2, both of which are withinmaxDiff. - Query
[2,3]: There is an edge between Node 2 and Node 3 because|nums[2] - nums[3]| = |6 - 8| = 2, which is equal tomaxDiff. - Thus, the final answer after processing all the queries is
[false, false, true, true].
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= 105numsis sorted in non-decreasing order.0 <= maxDiff <= 1051 <= queries.length <= 105queries[i] == [ui, vi]0 <= ui, vi < n
Approaches
3 approaches with complexity analysis and trade-offs.
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.
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
vis reached, a path exists.
Walkthrough
The algorithm for this approach is as follows:
- Initialize a boolean array
answerto store the results for each query. - For each query
[u, v]in thequeriesarray: 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 betweeniandjin the adjacency list. d. Use BFS or DFS, starting fromu, to traverse the graph. Keep track of visited nodes. e. Ifvis visited during the traversal, a path exists. Set the corresponding entry inanswertotrue. Otherwise, set it tofalse. - Return the
answerarray.
Here is a code snippet implementing this approach using BFS:
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a DSU structure for
nnodes. - Iterate through all pairs of nodes
(i, j). - If
|nums[i] - nums[j]| <= maxDiff, callunion(i, j). - For each query
[u, v], check iffind(u) == find(v).
Walkthrough
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.
- Initialize a DSU data structure with
nnodes, each in its own component. - Iterate through all unique pairs of nodes
(i, j). - If
|nums[i] - nums[j]| <= maxDiff, perform aunionoperation on nodesiandj. - After processing all pairs, the DSU structure will represent all the connected components of the graph.
- For each query
[u, v], use thefindoperation to check ifuandvhave the same representative (root). If they do, a path exists.
Here is a code snippet for this approach:
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; }}Complexity
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.
Trade-offs
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.
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).
Algorithm
- Initialize a DSU structure for
nnodes. - Iterate from
i = 0ton-2. - If
nums[i+1] - nums[i] <= maxDiff, callunion(i, i+1). - For each query
[u, v], check iffind(u) == find(v).
Walkthrough
The algorithm simplifies to building connected components based only on adjacent nodes in the sorted nums array.
- Initialize a DSU data structure with
nnodes. - Iterate through the
numsarray fromi = 0ton-2. - For each
i, ifnums[i+1] - nums[i] <= maxDiff, perform aunionoperation on nodesiandi+1. - This single pass is sufficient to capture all connectivity information.
- Process each query
[u, v]by checking iffind(u) == find(v).
The implementation is as follows:
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.