LeetCode Entry

3532. Path Existence Queries in a Graph I

09.07.2026 medium 2026 kotlin rust

Queries of connected nodes

3532. Path Existence Queries in a Graph I medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1415

Problem TLDR

Queries of connected nodes

Intuition

• build a Union-Find, iterate once, connect consequent numbers

Approach

• we can reuse the nums array

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun pathExistenceQueries(n: Int, ns: IntArray, md: Int, qs: Array<IntArray>) = run {
        ns.reduceIndexed { i, p, c -> c.also { if (c - p <= md) ns[i] = ns[i-1] } }
        qs.map { (a,b) -> ns[a]==ns[b] }
    }

    pub fn path_existence_queries(n: i32, mut ns: Vec<i32>, md: i32, qs: Vec<Vec<i32>>) -> Vec<bool> {
        let mut p = ns[0]; for i in 1..ns.len() { let n = ns[i]; if n - p <= md { ns[i] = ns[i-1]}; p = n }
        qs.iter().map(|q|ns[q[0] as usize]==ns[q[1] as usize]).collect()
    }