Checking existence of edge length limited paths

Array Two Pointers Union-Find Graph Theory Sorting

63.2% acceptance

Feb 25, 2026

2101

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

struct UnionFind {
  parent: Vec<usize>,
  rank: Vec<usize>,
}

impl UnionFind {
  fn new(n: usize) -> Self {
    UnionFind {
      parent: (0..n).collect(),
      rank: vec![0; n],
    }
  }
  fn find(&mut self, x: usize) -> usize {
    if self.parent[x] != x {
      self.parent[x] = self.find(self.parent[x]);
    }
    self.parent[x]
  }
  fn union(&mut self, x: usize, y: usize) {
    let px = self.find(x);
    let py = self.find(y);
    if px == py { return; }
    if self.rank[px] < self.rank[py] {
      self.parent[px] = py;
    } else if self.rank[px] > self.rank[py] {
      self.parent[py] = px;
    } else {
      self.parent[py] = px;
      self.rank[px] += 1;
    }
  }
  fn connected(&mut self, x: usize, y: usize) -> bool {
    self.find(x) == self.find(y)
  }
}

impl Solution {
  pub fn distance_limited_paths_exist(
    n: i32,
    edge_list: Vec<Vec<i32>>,
    queries: Vec<Vec<i32>>,
  ) -> Vec<bool> {
    let n = n as usize;
    let mut edges = edge_list;
    edges.sort_by_key(|e| e[2]);

    let q = queries.len();
    let mut idx: Vec<usize> = (0..q).collect();
    idx.sort_by_key(|&i| queries[i][2]);

    let mut uf = UnionFind::new(n);
    let mut ans = vec![false; q];
    let mut ei = 0usize;

    for &qi in &idx {
      let limit = queries[qi][2];
      while ei < edges.len() && edges[ei][2] < limit {
        uf.union(edges[ei][0] as usize, edges[ei][1] as usize);
        ei += 1;
      }
      let p = queries[qi][0] as usize;
      let r = queries[qi][1] as usize;
      ans[qi] = uf.connected(p, r);
    }
    ans
  }
}