#1627

Hard

LeetCode Problem Workspace

Graph Connectivity With Threshold

In 'Graph Connectivity With Threshold,' determine if cities are connected based on common divisors exceeding a threshold in given queries.

array math union find number theory

Problem Statement

You are given n cities labeled from 1 to n. Two cities are directly connected by a bidirectional road if and only if their labels share a common divisor strictly greater than a threshold. The task is to determine whether cities in a set of queries are connected, either directly or indirectly. A direct connection exists between cities a and b if there is a divisor z greater than the threshold such that z divides both a and b.

For each query in the form [a, b], you need to check if there is a path between city a and city b. If there is, return true; otherwise, return false. The challenge is to efficiently process the queries by considering the shared divisors of city labels and the threshold value provided.

Examples

Example 1

Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]

Output: [false,false,true]

The divisors for each number: 1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the only ones directly connected. The result of each query: [1,4] 1 is not connected to 4 [2,5] 2 is not connected to 5 [3,6] 3 is connected to 6 through path 3--6

Example 2

Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]

Output: [true,true,true,true,true]

The divisors for each number are the same as the previous example. However, since the threshold is 0, all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.

Example 3

Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]

Output: [false,false,false,false,false]

Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected. Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].

Constraints

2 <= n <= 104
0 <= threshold <= n
1 <= queries.length <= 105
queries[i].length == 2
1 <= ai, bi <= cities
ai != bi

Solution Approach

Union-Find Data Structure

Using the union-find (disjoint-set) data structure allows efficient management of city connections. The cities are initially unconnected, and by checking shared divisors greater than the threshold, cities can be grouped into connected components. Union operations merge components, and find operations determine if two cities belong to the same component.

Divisor Preprocessing

To optimize, preprocess divisors for all cities and organize them by the threshold. This allows quick determination of common divisors between city pairs, facilitating faster connection checks for each query. This approach reduces redundant calculations for each query.

Graph Construction with Threshold Constraints

Building a graph where each node represents a city and edges are determined by common divisors above the threshold is key. Once the graph is constructed, union-find operations can efficiently check if two cities are connected by direct or indirect paths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is primarily dependent on the union-find operations, which have near constant time complexity per operation due to path compression and union by rank. Preprocessing divisors adds an initial overhead, but once computed, queries can be answered quickly. The space complexity is determined by the size of the graph, which is proportional to n.

What Interviewers Usually Probe

Candidate should demonstrate understanding of divisor properties and efficient graph representation.
Look for clarity in explaining union-find data structure and its optimizations.
Assess candidate's ability to optimize by preprocessing divisors and minimizing redundant calculations.

Common Pitfalls or Variants

Common pitfalls

Failure to preprocess divisors efficiently, leading to excessive computation for each query.
Overcomplicating the solution with unnecessary data structures or algorithms.
Not handling edge cases such as cities with no common divisors greater than the threshold.

Follow-up variants

Different thresholds or varying divisor conditions (e.g., prime numbers only).
Handling larger inputs with constraints on query counts and city numbers.
Optimizing for multiple threshold values in a single run to answer all queries efficiently.

FAQ

What is the main pattern in Graph Connectivity With Threshold?

The problem combines array manipulation and math, specifically focusing on divisor properties, and leverages the union-find data structure for efficient query handling.

How do I handle multiple queries efficiently in this problem?

Preprocess divisors for all cities and then use union-find to quickly answer connectivity queries based on shared divisors exceeding the threshold.

What is the time complexity of this problem?

The time complexity is mainly dominated by the union-find operations, which are nearly constant time due to optimizations like path compression and union by rank.

Can this problem be solved without union-find?

While it is theoretically possible to solve it with other graph traversal methods, union-find is the most efficient approach for managing dynamic connectivity in this problem.

What should I focus on to solve Graph Connectivity With Threshold?

Focus on understanding the divisor properties, the threshold conditions, and efficiently applying union-find to manage the connectivity between cities.

terminal

Solution

Solution 1: Union-Find

We can enumerate $z$ and its multiples, and use union-find to connect them. In this way, for each query $[a, b]$, we only need to determine whether $a$ and $b$ are in the same connected component.

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

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

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def areConnected(
        self, n: int, threshold: int, queries: List[List[int]]
    ) -> List[bool]:
        uf = UnionFind(n + 1)
        for a in range(threshold + 1, n + 1):
            for b in range(a + a, n + 1, a):
                uf.union(a, b)
        return [uf.find(a) == uf.find(b) for a, b in queries]

Continue Practicing

#1998 gcd sort of an array #952 largest component size by common factor #1569 number of ways to reorder array to get same bst