LeetCode 1627 - Graph Connectivity With Threshold

Difficulty: 🔴 Hard
Topics: Array, Math, Union-Find, Number Theory

Solution

Problem Understanding

The problem gives us n cities labeled from 1 to n. Two cities are directly connected if they share a common divisor that is strictly greater than a given threshold.

For example, if threshold = 2, then cities 6 and 9 are directly connected because they share divisor 3, and 3 > 2. However, cities 4 and 6 are not directly connected because their greatest shared divisor greater than 1 is 2, which is not strictly greater than 2.

The key detail is that the problem does not only ask whether two cities are directly connected, it asks whether they are connected directly or indirectly. This means we are looking for connectivity inside an undirected graph. If city A connects to city B, and city B connects to city C, then A and C are considered connected even if they do not share a valid divisor themselves.

The input consists of three parts:

n, representing the number of cities.
threshold, which determines which divisors are valid for creating roads.
queries, where each query [a, b] asks whether city a and city b belong to the same connected component.

The output is a boolean array where each entry corresponds to a query. If two cities are connected through any path, we return true; otherwise, we return false.

The constraints are very important for choosing an algorithm:

n <= 10^4
queries.length <= 10^5

A naive graph construction that compares every pair of cities would require O(n²) comparisons, and checking divisors for each pair makes it even slower. Since queries can reach 100,000, we need a way to preprocess connectivity efficiently and answer each query quickly.

Several edge cases stand out immediately:

When threshold = 0, every number shares divisor 1, and since 1 > 0, all cities become connected.
When threshold = n, no divisor can be greater than n, meaning no roads exist.
City 1 behaves differently because it only has divisor 1, so it often becomes isolated unless threshold = 0.
Multiple identical queries may appear, and queries are symmetric, meaning [a, b] is equivalent to [b, a].

Approaches

Brute Force Approach

The most direct approach is to explicitly build the graph.

For every pair of cities (x, y), we compute their greatest common divisor (GCD). If gcd(x, y) > threshold, we add an edge between them. After constructing the graph, we answer each query using graph traversal such as BFS or DFS to check whether two cities are connected.

This works because the graph definition exactly matches the problem statement. Every valid pair receives an edge, and connectivity queries are simply graph reachability problems.

However, this approach is far too slow.

There are O(n²) city pairs. For each pair, computing the GCD costs O(log n). Then, for every query, performing BFS or DFS may cost O(n + e).

With n = 10^4, an O(n²) graph construction becomes approximately 10^8 operations, which is already too expensive.

Optimal Approach, Union-Find with Divisor Multiples

The key observation is that we do not need to compare every pair of cities.

Suppose a divisor d > threshold exists. Any cities divisible by d are directly connected because they share divisor d.

For example:

If d = 3, then 3, 6, 9, 12... should all belong to the same connected component.
Instead of checking every pair, we can connect all multiples of d.

This resembles the Sieve of Eratosthenes idea. For every divisor d from threshold + 1 to n, we union all multiples of d.

For example, when d = 4:

Connect 4 with 8
Connect 4 with 12
Connect 4 with 16

All multiples become part of the same connected component.

To efficiently maintain connected components, we use a Union-Find (Disjoint Set Union, DSU) structure.

Union-Find supports:

union(a, b) to merge components
find(x) to determine a component representative

After preprocessing, answering each query becomes simple:

Two cities are connected if:

find(a) == find(b)

This transforms expensive graph traversals into nearly constant-time lookups.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² log n + q(n + e))	O(n²)	Explicit graph construction and traversal
Optimal	O(n log log n + qα(n))	O(n)	Union-Find over divisor multiples

Here, α(n) is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

Step 1: Initialize Union-Find

Create a parent array where each city initially belongs to its own set.

For example:

parent = [0,1,2,3,4,5,6]

Each node starts disconnected.

We also use path compression so repeated lookups become very fast.

Step 2: Iterate Through Valid Divisors

Loop from:

threshold + 1

to:

Only divisors strictly greater than the threshold matter.

Step 3: Connect Multiples of Each Divisor

For each divisor d, connect all multiples:

d, 2d, 3d, 4d...

We repeatedly union:

union(d, multiple)

For example:

If:

n = 12
threshold = 2

For divisor 3:

union(3,6)
union(3,9)
union(3,12)

For divisor 4:

union(4,8)
union(4,12)

This guarantees that every number sharing divisor d ends up inside the same component.

Step 4: Answer Queries

For every query [a, b]:

Find representative of a
Find representative of b
Compare them

If representatives match:

True

Otherwise:

False

Why it works

The algorithm works because every valid road exists due to some divisor d > threshold.

By iterating through every such divisor and unioning all of its multiples, we guarantee that any directly connected cities are merged into the same component. Since Union-Find preserves transitive connectivity, indirectly connected cities also end up in the same set.

Therefore, two cities are connected if and only if their representatives are equal.

Python Solution

from typing import List

class Solution:
    def areConnected(
        self,
        n: int,
        threshold: int,
        queries: List[List[int]]
    ) -> List[bool]:

        parent = list(range(n + 1))

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)

            if root_a != root_b:
                parent[root_b] = root_a

        # Connect multiples of each valid divisor
        for divisor in range(threshold + 1, n + 1):
            multiple = divisor * 2

            while multiple <= n:
                union(divisor, multiple)
                multiple += divisor

        result = []

        for city_a, city_b in queries:
            result.append(find(city_a) == find(city_b))

        return result

The implementation starts by initializing the Union-Find structure. Each city is its own parent initially because no connections have been processed yet.

The find() function performs path compression. Whenever we search for a representative, intermediate nodes are updated to point directly to the root. This dramatically improves performance for repeated operations.

The union() function merges two components. If two cities already belong to the same set, no work is needed.

The preprocessing phase loops through every divisor greater than the threshold. Instead of comparing every pair of cities, it connects only multiples of the divisor. This is the core optimization.

Finally, each query becomes a constant-time connectivity check by comparing component representatives.

Go Solution

func areConnected(n int, threshold int, queries [][]int) []bool {
	parent := make([]int, n+1)

	for i := 0; i <= n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(a int, b int) {
		rootA := find(a)
		rootB := find(b)

		if rootA != rootB {
			parent[rootB] = rootA
		}
	}

	// Connect multiples of each valid divisor
	for divisor := threshold + 1; divisor <= n; divisor++ {
		for multiple := divisor * 2; multiple <= n; multiple += divisor {
			union(divisor, multiple)
		}
	}

	result := make([]bool, len(queries))

	for i, query := range queries {
		a := query[0]
		b := query[1]

		result[i] = find(a) == find(b)
	}

	return result
}

The Go solution follows the same logic as the Python version.

The biggest difference is function handling. Since Go does not support nested named functions as conveniently as Python, find is declared as a function variable to allow recursion.

Slices are used for both the parent array and the result list. Since integers in Go are already large enough for the problem constraints, integer overflow is not a concern.

Unlike Python, Go requires explicit allocation for the result slice:

result := make([]bool, len(queries))

This avoids repeated append operations and improves efficiency.

Worked Examples

Example 1

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

Valid divisors:

3, 4, 5, 6

Initial state:

City	Parent
1	1
2	2
3	3
4	4
5	5
6	6

Process divisor 3:

Multiples:

3, 6

Union:

union(3,6)

Parent becomes:

City	Parent
1	1
2	2
3	3
4	4
5	5
6	3

Process divisor 4:

No multiples greater than 4 within range.

Process divisor 5:

No multiples.

Process divisor 6:

No multiples.

Queries:

Query	Connected?
[1,4]	False
[2,5]	False
[3,6]	True

Output:

[false, false, true]

Example 2

n = 6
threshold = 0

Every divisor greater than 0 works.

Divisor 1 immediately connects:

1,2,3,4,5,6

Everything becomes one component.

Queries:

Query	Connected?
[4,5]	True
[3,4]	True
[3,2]	True
[2,6]	True
[1,3]	True

Output:

[true, true, true, true, true]

Example 3

n = 5
threshold = 1

Valid divisors:

2,3,4,5

For divisor 2:

union(2,4)

For divisors 3, 4, 5:

No valid multiples.

Final connected component:

{2,4}

Queries:

Query	Connected?
[4,5]	False
[4,5]	False
[3,2]	False
[2,3]	False
[3,4]	False

Output:

[false, false, false, false, false]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log log n + qα(n))	Union operations over divisor multiples, plus near constant query checks
Space	O(n)	Parent array for Union-Find

The preprocessing phase resembles a sieve. The number of union operations is:

n/2 + n/3 + n/4 + ...

This harmonic behavior leads to approximately O(n log log n) complexity.

Each query performs two find() operations, which are nearly constant because of path compression.

Test Cases

solution = Solution()

# Example 1
assert solution.areConnected(
    6, 2, [[1, 4], [2, 5], [3, 6]]
) == [False, False, True]  # basic threshold example

# Example 2
assert solution.areConnected(
    6, 0, [[4, 5], [3, 4], [3, 2], [2, 6], [1, 3]]
) == [True, True, True, True, True]  # threshold zero, all connected

# Example 3
assert solution.areConnected(
    5, 1, [[4, 5], [4, 5], [3, 2], [2, 3], [3, 4]]
) == [False, False, False, False, False]  # duplicate queries

# Threshold equals n
assert solution.areConnected(
    5, 5, [[1, 2], [3, 4]]
) == [False, False]  # no connections possible

# Single meaningful divisor
assert solution.areConnected(
    10, 4, [[5, 10], [6, 9]]
) == [True, False]  # divisor 5 connects only multiples of 5

# Indirect connection
assert solution.areConnected(
    12, 2, [[3, 12]]
) == [True]  # connected through divisor chain

# City 1 isolation
assert solution.areConnected(
    10, 1, [[1, 2], [1, 10]]
) == [False, False]  # city 1 disconnected

# Large connectivity via divisor 2
assert solution.areConnected(
    8, 1, [[2, 8], [4, 6]]
) == [True, True]  # even numbers connected

# No valid divisor
assert solution.areConnected(
    7, 6, [[2, 7]]
) == [False]  # threshold prevents all edges

Test	Why
Example 1	Verifies normal connectivity behavior
Example 2	Validates `threshold = 0` edge case
Example 3	Confirms duplicate queries behave correctly
`threshold = n`	Ensures no roads are created
Single divisor case	Tests isolated divisor grouping
Indirect connection	Verifies transitive connectivity
City `1` isolation	Ensures special divisor behavior
Even-number grouping	Confirms large component merging
No valid divisor	Tests complete disconnection

Edge Cases

Threshold Equals Zero

When threshold = 0, divisor 1 becomes valid because 1 > 0.

Since every number is divisible by 1, all cities become part of the same connected component. A buggy implementation might accidentally ignore divisor 1, causing incorrect disconnected results. This implementation handles it naturally because iteration begins at:

threshold + 1

which becomes 1.

Threshold Equals `n`

If threshold = n, no divisor can be strictly greater than the threshold. Therefore, no roads exist at all.

A naive implementation might still attempt unnecessary union operations or accidentally connect nodes. In this solution, the divisor loop becomes empty:

range(n + 1, n + 1)

so every city remains isolated.

City `1` Being Isolated

City 1 only has divisor 1.

If threshold >= 1, city 1 cannot share any valid divisor with another city, meaning it always remains disconnected. This can easily cause mistakes if the implementation assumes every city eventually joins a component.

The Union-Find setup naturally handles this because city 1 never appears in any union operation unless divisor 1 is valid.

Duplicate Queries

The problem allows repeated queries such as:

[4,5]
[4,5]

A less efficient solution might recompute graph traversal each time. Since Union-Find preprocessing happens once, duplicate queries are answered in constant time with no extra cost.

Indirect Connectivity

Two cities may not share a divisor directly but still be connected through intermediate cities.

For example:

3 -> 6 -> 12

A buggy implementation that only checks direct divisibility would fail. Union-Find correctly merges entire connected components, preserving transitive connectivity automatically.

LeetCode 1627 - Graph Connectivity With Threshold

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach, Union-Find with Divisor Multiples

Algorithm Walkthrough

Step 1: Initialize Union-Find

Step 2: Iterate Through Valid Divisors

Step 3: Connect Multiples of Each Divisor

Step 4: Answer Queries

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Edge Cases

Threshold Equals Zero

Threshold Equals n

City 1 Being Isolated

Duplicate Queries

Indirect Connectivity

Threshold Equals `n`

City `1` Being Isolated