Scale Engineer

Checking Existence of Edge Length Limited Paths

Hard
#1556Time: O(Q * (N + E)), where Q is the number of queries, N is the number of nodes, and E is the number of edges. For each of the Q queries, we iterate through all E edges to build the graph (O(E)) and then perform a traversal (O(N+E)).Space: O(N + E) per query. In each iteration, we build an adjacency list which can take up to O(E) space, and the BFS requires O(N) space for the `visited` array and the queue.
Patterns
Two Pointers
Algorithms
SortingUnion Find
Data structures
ArrayGraph

Prompt

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

 

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Explanation: The above figure shows the given graph.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= edgeList.length, queries.length <= 105
  • edgeList[i].length == 3
  • queries[j].length == 3
  • 0 <= ui, vi, pj, qj <= n - 1
  • ui != vi
  • pj != qj
  • 1 <= disi, limitj <= 109
  • There may be multiple edges between two nodes.

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to process each query independently. For every query, we can construct a new graph that only includes edges with weights strictly less than the query's limit. After building this subgraph, we can use a standard graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to determine if a path exists between the two specified nodes.

Algorithm

  • Create a boolean array answer of size queries.length.
  • For each query j from 0 to queries.length - 1:
    • Let p = queries[j][0], q = queries[j][1], limit = queries[j][2].
    • Build an adjacency list adj for a graph with n nodes.
    • For each edge (u, v, dist) in edgeList:
      • If dist < limit, add v to adj[u] and u to adj[v].
    • Use BFS or DFS to check if q is reachable from p in the graph represented by adj.
    • If reachable, set answer[j] = true, otherwise answer[j] = false.
  • Return answer.

Walkthrough

For each query (p, q, limit):

  1. Initialize an empty adjacency list to represent the graph for this specific query.
  2. Iterate through the entire edgeList. If an edge's weight is less than the given limit, add it to the adjacency list.
  3. Once the graph is constructed, perform a BFS starting from node p.
  4. Use a visited array to keep track of nodes already visited to avoid cycles and redundant work.
  5. A queue is used for the BFS. Initially, it contains only the start node p.
  6. In a loop, dequeue a node. If this node is the target node q, we have found a path, and the result for this query is true.
  7. If the node is not the target, add all of its unvisited neighbors to the queue and mark them as visited.
  8. If the queue becomes empty and q has not been reached, it means there is no path between p and q under the given limit. The result is false.
  9. This process is repeated for all queries.
import java.util.*; class Solution {    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {        int qLen = queries.length;        boolean[] answer = new boolean[qLen];         for (int i = 0; i < qLen; i++) {            int p = queries[i][0];            int q = queries[i][1];            int limit = queries[i][2];             // Build graph for the current query            List<List<Integer>> adj = new ArrayList<>();            for (int j = 0; j < n; j++) {                adj.add(new ArrayList<>());            }            for (int[] edge : edgeList) {                if (edge[2] < limit) {                    adj.get(edge[0]).add(edge[1]);                    adj.get(edge[1]).add(edge[0]);                }            }             // Check connectivity using BFS            answer[i] = bfs(p, q, n, adj);        }        return answer;    }     private boolean bfs(int start, int end, int n, List<List<Integer>> adj) {        if (start == end) return true;        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 + E)), where Q is the number of queries, N is the number of nodes, and E is the number of edges. For each of the Q queries, we iterate through all E edges to build the graph (O(E)) and then perform a traversal (O(N+E)).

Space

O(N + E) per query. In each iteration, we build an adjacency list which can take up to O(E) space, and the BFS requires O(N) space for the `visited` array and the queue.

Trade-offs

Pros

  • Simple to conceptualize and implement.

Cons

  • Highly inefficient due to redundant computations.

  • Will result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {private  int[] p;public  boolean[] distanceLimitedPathsExist(int n, int[][] edgeList,                                      int[][] queries) {    p = new int[n];    for (int i = 0; i < n; ++i) {      p[i] = i;    }    Arrays.sort(edgeList, (a, b)->a[2] - b[2]);    int m = queries.length;    boolean[] ans = new boolean[m];    Integer[] qid = new Integer[m];    for (int i = 0; i < m; ++i) {      qid[i] = i;    }    Arrays.sort(qid, (i, j)->queries[i][2] - queries[j][2]);    int j = 0;    for (int i : qid) {      int a = queries[i][0], b = queries[i][1], limit = queries[i][2];      while (j < edgeList.length && edgeList[j][2] < limit) {        int u = edgeList[j][0], v = edgeList[j][1];        p[find(u)] = find(v);        ++j;      }      ans[i] = find(a) == find(b);    }    return ans;  }private  int find(int x) {    if (p[x] != x) {      p[x] = find(p[x]);    }    return p[x];  }}

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