Path existence queries in a graph i

Array Hash Table Binary Search Union-Find Graph Theory

55.3% acceptance

Feb 25, 2026

109

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 |nums[i] - nums[j]| <= maxDiff. For each queries[i] = [ui, vi], determine whether there exists a path between nodes ui and vi. Return a boolean array answer.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn path_existence_queries(
    _n: i32,
    nums: Vec<i32>,
    max_diff: i32,
    queries: Vec<Vec<i32>>,
  ) -> Vec<bool> {
    // Since nums is sorted, nodes i and i+1 are connected iff nums[i+1]-nums[i] <= maxDiff
    // Connected components are contiguous ranges with no gap > maxDiff between consecutive elements
    let n = nums.len();
    let mut comp = vec![0u32; n];
    let mut cur = 0u32;
    for i in 1..n {
      if nums[i] - nums[i - 1] > max_diff {
        cur += 1;
      }
      comp[i] = cur;
    }

    queries
      .iter()
      .map(|q| comp[q[0] as usize] == comp[q[1] as usize])
      .collect()
  }
}