DDSA Solutions

3532. Path Existence Queries in a Graph I

MediumView on LeetCode
Union FindArrayGraph

Problem Overview

Nodes i and j are connected when |nums[i] − nums[j]| ≤ maxDiff.

Intuition

Nodes i and j are connected when |nums[i] − nums[j]| ≤ maxDiff. Because nums is sorted, any path stays inside a contiguous block of indices: if two indices are in the same component, every index between them is too. So only check consecutive pairs — union i with i−1 when their values are close enough, then answer queries by comparing DSU roots.

Algorithm

  1. 1Initialize Union-Find on n nodes.
  2. 2For i = 1 … n−1: if nums[i] − nums[i−1] ≤ maxDiff, union(i, i−1).
  3. 3For each query [u, v]: answer[i] = (Find(u) == Find(v)).
  4. 4Equivalently, label each contiguous “good-gap” segment with one component id.

Example Walkthrough

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

  1. 1.Adjacent gaps: |5−2|=3 > 2 → break after index 0. |6−5|=1 and |8−6|=2 → indices 1–3 form one component.
  2. 2.Component ids: [0, 1, 1, 1].
  3. 3.Query [0,1]: different components → false.
  4. 4.Query [0,2]: 0 vs component 1 → false.
  5. 5.Query [1,3]: same component → true (path 1→2→3).
  6. 6.Query [2,3]: same component → true (direct edge).

Output: [false, false, true, true]

Common Pitfalls

  • •Only adjacent unions are enough because nums is sorted — do not union all pairs O(n²).
  • •Use nums[i] − nums[i−1] (non-negative) instead of Math.Abs on sorted input.
  • •Self-queries [u,u] are always true once a node is in its own set.
3532.cs
C#
// Approach: nums is sorted, so connected components are contiguous index ranges where each
// adjacent gap satisfies |nums[i] - nums[i-1]| <= maxDiff. Union those neighbors in DSU;
// each query is true iff Find(u) == Find(v).
// Time: O(n α(n) + q) Space: O(n)
public class Solution
{
    public bool[] PathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries)
    {
        bool[] ans = new bool[queries.Length];
        UnionFind uf = new UnionFind(n);

        for (int i = 1; i < n; ++i)
        {
            if (Math.Abs(nums[i] - nums[i - 1]) <= maxDiff)
                uf.UnionByRank(i, i - 1);
        }

        for (int i = 0; i < queries.Length; ++i)
        {
            int u = queries[i][0];
            int v = queries[i][1];
            ans[i] = uf.Find(u) == uf.Find(v);
        }

        return ans;
    }
}

public class UnionFind
{
    private int[] id;
    private int[] rank;

    public UnionFind(int n)
    {
        id = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; ++i)
            id[i] = i;
    }

    public void UnionByRank(int u, int v)
    {
        int i = Find(u);
        int j = Find(v);
        if (i == j)
            return;
        if (rank[i] < rank[j])
            id[i] = j;
        else if (rank[i] > rank[j])
            id[j] = i;
        else
        {
            id[i] = j;
            ++rank[j];
        }
    }

    public int Find(int u)
    {
        if (id[u] == u)
            return u;
        return id[u] = Find(id[u]);
    }
}
Was this solution helpful?

Related Problems