Path Existence Queries in a Graph II

• For each query (u, v) in queries:
  • Initialize a queue and add (u, 0) (node, distance).
  • Initialize a distance array of size n with -1.
  • Set distance[u] = 0.
  • While the queue is not empty:
    • Dequeue the current node curr.
    • If curr is v, the shortest distance is found. Store it and break the loop.
    • Iterate through all nodes j from 0 to n-1:
      • If j is unvisited (distance[j] == -1) and |nums[curr] - nums[j]| <= maxDiff:
        • Set distance[j] = distance[curr] + 1.
        • Enqueue j.
  • If v was not reached, the distance is -1.
• Return the array of computed distances.

The algorithm for each query [u, v] is as follows:

1. Initialize a queue for the BFS and add the starting node u with a distance of 0.
2. Use a visited array or set to keep track of nodes that have already been added to the queue, to avoid cycles and redundant computations. Mark u as visited.
3. Use a distance array to store the shortest distance from u to every other node, initialized to infinity except for distance[u] = 0.
4. While the queue is not empty, dequeue a node curr.
5. If curr is the target node v, we have found the shortest path. The distance is distance[curr]. We can terminate the BFS for this query and return the result.
6. If curr is not the target, we need to find all its neighbors. We iterate through all other nodes j from 0 to n-1.
7. For each node j, if it has not been visited and an edge exists between curr and j (i.e., |nums[curr] - nums[j]| <= maxDiff), we mark j as visited, update its distance (distance[j] = distance[curr] + 1), and enqueue it.
8. If the queue becomes empty and we have not reached v, it means there is no path between u and v. In this case, the distance is -1.

This entire process is repeated for every query in the queries array.

1class Solution {2    public int[] minDistance(int n, int[] nums, int maxDiff, int[][] queries) {3        int[] answer = new int[queries.length];4        for (int i = 0; i < queries.length; i++) {5            answer[i] = bfs(queries[i][0], queries[i][1], n, nums, maxDiff);6        }7        return answer;8    }9 10    private int bfs(int start, int end, int n, int[] nums, int maxDiff) {11        if (start == end) {12            return 0;13        }14 15        Queue<Integer> queue = new LinkedList<>();16        int[] dist = new int[n];17        Arrays.fill(dist, -1);18 19        queue.offer(start);20        dist[start] = 0;21 22        while (!queue.isEmpty()) {23            int u = queue.poll();24 25            if (u == end) {26                return dist[u];27            }28 29            // Find neighbors by iterating through all nodes30            for (int v = 0; v < n; v++) {31                if (dist[v] == -1 && Math.abs(nums[u] - nums[v]) <= maxDiff) {32                    dist[v] = dist[u] + 1;33                    queue.offer(v);34                }35            }36        }37 38        return -1;39    }40}

• For each query (u, v):
  • Initialize a data structure (e.g., a BBST or a list of TreeSets for each value) containing all unvisited nodes, structured for efficient range queries on nums values.
  • Initialize a queue, a distance array, and a visited array.
  • Add u to the queue, set its distance to 0, mark it as visited, and remove it from the unvisited data structure.
  • While the queue is not empty:
    • Dequeue curr.
    • If curr is v, return its distance.
    • Perform a range query on the unvisited data structure for [nums[curr] - maxDiff, nums[curr] + maxDiff].
    • For each node j found in the range:
      • Remove j from the unvisited data structure.
      • Set distance[j] = distance[curr] + 1 and enqueue j.
  • If v was not reached, return -1.

The improved algorithm for each query (u, v) is as follows:

1. To handle nodes with the same nums value, we create pairs of (value, index) for each node.
2. For each query, we populate a BBST (e.g., TreeSet) with pairs (nums[i], i) for all nodes i that are yet to be visited. The TreeSet will keep the nodes sorted by their nums value, and then by index as a tie-breaker.
3. Start a BFS from node u. Initialize a queue and a distance array.
4. Remove (nums[u], u) from the TreeSet and add u to the queue.
5. While the queue is not empty, dequeue a node curr.
6. To find its neighbors, perform a range query on the TreeSet for the value range [nums[curr] - maxDiff, nums[curr] + maxDiff].
7. The TreeSet efficiently provides all nodes within this value range. For each neighbor found: a. Remove it from the TreeSet to mark it as visited. b. Update its distance and add it to the queue.
8. This process continues until the destination v is found or the queue is empty.

Each node is added to the queue once and removed from the TreeSet once. The cost of finding neighbors for a node is dominated by the range query on the TreeSet, which is O(log N + K), where K is the number of neighbors found. Summed over the entire BFS, this leads to a much better time complexity per query.

1class Solution {2    public int[] minDistance(int n, int[] nums, int maxDiff, int[][] queries) {3        // Pre-sort nodes by value to potentially group nodes with same value4        List<List<Integer>> valToNodes = new ArrayList<>();5        for (int i = 0; i < 100001; i++) {6            valToNodes.add(new ArrayList<>());7        }8        for (int i = 0; i < n; i++) {9            valToNodes.get(nums[i]).add(i);10        }11 12        int[] answer = new int[queries.length];13        for (int i = 0; i < queries.length; i++) {14            answer[i] = bfsWithDS(queries[i][0], queries[i][1], n, nums, maxDiff, valToNodes);15        }16        return answer;17    }18 19    private int bfsWithDS(int start, int end, int n, int[] nums, int maxDiff, List<List<Integer>> valToNodes) {20        if (start == end) {21            return 0;22        }23 24        Queue<Integer> queue = new LinkedList<>();25        int[] dist = new int[n];26        Arrays.fill(dist, -1);27 28        // Use a data structure for unvisited nodes. A TreeSet of values works.29        TreeSet<Integer> unvisitedValues = new TreeSet<>();30        for (int val : nums) {31            unvisitedValues.add(val);32        }33        // We need a way to mark nodes as visited, not just values.34        boolean[] visited = new boolean[n];35 36        queue.offer(start);37        dist[start] = 0;38        visited[start] = true;39 40        while (!queue.isEmpty()) {41            int u = queue.poll();42 43            if (u == end) {44                return dist[u];45            }46 47            int low = Math.max(0, nums[u] - maxDiff);48            int high = Math.min(100000, nums[u] + maxDiff);49 50            // Query the TreeSet for the range of values51            Integer nextVal = unvisitedValues.ceiling(low);52            while (nextVal != null && nextVal <= high) {53                for (int v : valToNodes.get(nextVal)) {54                    if (!visited[v]) {55                        visited[v] = true;56                        dist[v] = dist[u] + 1;57                        queue.offer(v);58                    }59                }60                // Once all nodes for a value are visited, remove the value from the set61                unvisitedValues.remove(nextVal);62                nextVal = unvisitedValues.ceiling(low);63            }64        }65 66        return -1;67    }68}

Note: The provided Java code snippet illustrates the concept. A fully optimized implementation might require careful handling of removing nodes from the valToNodes lists or using a more complex structure to avoid re-visiting nodes with the same value.