Scale Engineer

Path Existence Queries in a Graph II

Hard
#3145Time: O(Q * N^2), where Q is the number of queries and N is the number of nodes. For each of the Q queries, we perform a BFS. A single BFS can take up to O(N^2) time because for each of the N nodes, we might iterate through all N other nodes to find its neighbors.Space: O(N) for each BFS run to store the queue, distance array, and visited set. Since we run queries sequentially, the space can be reused.
Patterns
Greedy
Algorithms
Binary SearchSorting
Data structures
ArrayGraph

Prompt

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 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], find the minimum distance between nodes ui and vi. If no path exists between the two nodes, return -1 for that query.

Return an array answer, where answer[i] is the result of the ith query.

Note: The edges between the nodes are unweighted.

 

Example 1:

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

Output: [1,1]

Explanation:

The resulting graph is:

Query Shortest Path Minimum Distance
[0, 3] 0 → 3 1
[2, 4] 2 → 4 1

Thus, the output is [1, 1].

Example 2:

Input: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]

Output: [1,2,-1,1]

Explanation:

The resulting graph is:

Query Shortest Path Minimum Distance
[0, 1] 0 → 1 1
[0, 2] 0 → 1 → 2 2
[2, 3] None -1
[4, 3] 3 → 4 1

Thus, the output is [1, 2, -1, 1].

Example 3:

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

Output: [0,-1,-1]

Explanation:

There are no edges between any two nodes because:

  • Nodes 0 and 1: |nums[0] - nums[1]| = |3 - 6| = 3 > 1
  • Nodes 0 and 2: |nums[0] - nums[2]| = |3 - 1| = 2 > 1
  • Nodes 1 and 2: |nums[1] - nums[2]| = |6 - 1| = 5 > 1

Thus, no node can reach any other node, and the output is [0, -1, -1].

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 105
  • 0 <= maxDiff <= 105
  • 1 <= queries.length <= 105
  • queries[i] == [ui, vi]
  • 0 <= ui, vi < n

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to treat the problem as a series of shortest path queries on an implicitly defined graph. For each query [u, v], we can run a Breadth-First Search (BFS) starting from node u to find the shortest distance to node v. BFS is suitable here because all edges are unweighted, meaning each edge contributes 1 to the path length.

Algorithm

  • 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.

Walkthrough

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.

class Solution {    public int[] minDistance(int n, int[] nums, int maxDiff, int[][] queries) {        int[] answer = new int[queries.length];        for (int i = 0; i < queries.length; i++) {            answer[i] = bfs(queries[i][0], queries[i][1], n, nums, maxDiff);        }        return answer;    }     private int bfs(int start, int end, int n, int[] nums, int maxDiff) {        if (start == end) {            return 0;        }         Queue<Integer> queue = new LinkedList<>();        int[] dist = new int[n];        Arrays.fill(dist, -1);         queue.offer(start);        dist[start] = 0;         while (!queue.isEmpty()) {            int u = queue.poll();             if (u == end) {                return dist[u];            }             // Find neighbors by iterating through all nodes            for (int v = 0; v < n; v++) {                if (dist[v] == -1 && Math.abs(nums[u] - nums[v]) <= maxDiff) {                    dist[v] = dist[u] + 1;                    queue.offer(v);                }            }        }         return -1;    }}

Complexity

Time

O(Q * N^2), where Q is the number of queries and N is the number of nodes. For each of the Q queries, we perform a BFS. A single BFS can take up to O(N^2) time because for each of the N nodes, we might iterate through all N other nodes to find its neighbors.

Space

O(N) for each BFS run to store the queue, distance array, and visited set. Since we run queries sequentially, the space can be reused.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Very inefficient due to its high time complexity.

  • The neighbor finding step, which iterates through all n nodes, is a major bottleneck.

  • Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

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.

← Previous

Previous problem

Next →

Next problem