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.
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; }}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.