3532.Path_Existence_Queries_in_a_Graph_I(Medium).md

3532. Path Existence Queries in a Graph I (Medium)

Date and Time: Apr 26, 2025

Link: https://leetcode.com/problems/path-existence-queries-in-a-graph-i

Walk-through:

1. Build a Union Find data structue to store nodes that have path exist.

2. We start at 1, then we calculate if there exists path between i with i-1 by calculating the difference abs(nums[i] - nums[i-1]), if diff <= maxDiff, we can call uf.union(i, i-1) to connect these two nodes together.

3. Then, we can traverse each query with (u, v) to compare their roots by checking if uf.find(u) == uf.find(v). If they have path exist, they must equal (they have the same root).
   
   We handle the case on [0, 0], because when we call on uf.find(), they will be equal.

Union Find:

class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if x != self.root[x]:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            elif self.rank[rootY] < self.rank[rootX]:
                self.root[rootY] = rootX
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        # Q: Check if queries exist path
        # S: 1. Use Union-Find() to build each connected-component
        # 2. For each query (u, v), check if uf.find(u) == uf.find(v). If they have the same root, we know there exists path
        # TC: O(n), SC: O(n)
        
        uf = UnionFind(n)
        # Add connected components from 0 to n-1
        for i in range(1, n):
            if abs(nums[i] - nums[i-1]) <= maxDiff:
                uf.union(i-1, i)
        # Use uf to compare u, v from each query
        ans = []
        for u, v in queries:
            ans.append(uf.find(u) == uf.find(v))
        return ans

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Java

class UnionFind {
    // Declaration
    List<Integer> root = new ArrayList<>();
    List<Integer> rank = new ArrayList<>();
    int n;

    // Constructor to initialize n, root, rank
    public UnionFind(int n) {
        this.n = n;
        for (int i = 0; i < n; i++) {
            root.add(i);
            rank.add(1);
        }
    }

    public int find(int x) {
        if (x != root.get(x)) {
            root.set(x, find(root.get(x)));
        }
        return root.get(x);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // If rootX rank < rootY rank, update rootX's root to rootY
            if (rank.get(rootX) < rank.get(rootY)) {
                root.set(rootX, rootY);
            } else if (rank.get(rootY) < rank.get(rootX)) {
                root.set(rootY, rootX);
            } else {
                root.set(rootX, rootY);
                rank.set(rootY, rank.get(rootY)+1);
            }
        }
    }
}

class Solution {
    /* 
    1. Use UF to add nodes from [0, n-1] together
    2. Check each query (u, v) if they have same root so we know if path exists or not
    TC: O(n), SC: O(n)
    */
    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        // Union Find Data structure
        UnionFind uf = new UnionFind(n);
        // 1. Connect two nodes by UF
        for (int i=1; i < n; i++) {
            if (Math.abs(nums[i] - nums[i-1]) <= maxDiff) {
                uf.union(i, i-1);
            }
        }
        // 2. Search queries for u, v
        boolean[] ans = new boolean[queries.length];
        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;
    }
}