Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:
x % z == 0,y % z == 0, andz > threshold.Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them).
Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.
Example 1:
Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]] Output: [false,false,true] Explanation: 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] Explanation: 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] Explanation: 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 <= 1040 <= threshold <= n1 <= queries.length <= 105queries[i].length == 21 <= ai, bi <= citiesai != biProblem summary: We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true: x % z == 0, y % z == 0, and z > threshold. Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them). Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Union-Find
6 2 [[1,4],[2,5],[3,6]]
6 0 [[4,5],[3,4],[3,2],[2,6],[1,3]]
5 1 [[4,5],[4,5],[3,2],[2,3],[3,4]]
greatest-common-divisor-traversal)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1627: Graph Connectivity With Threshold
class UnionFind {
private int[] p;
private int[] size;
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
}
class Solution {
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
UnionFind uf = new UnionFind(n + 1);
for (int a = threshold + 1; a <= n; ++a) {
for (int b = a + a; b <= n; b += a) {
uf.union(a, b);
}
}
List<Boolean> ans = new ArrayList<>();
for (var q : queries) {
ans.add(uf.find(q[0]) == uf.find(q[1]));
}
return ans;
}
}
// Accepted solution for LeetCode #1627: Graph Connectivity With Threshold
type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func areConnected(n int, threshold int, queries [][]int) []bool {
uf := newUnionFind(n + 1)
for a := threshold + 1; a <= n; a++ {
for b := a + a; b <= n; b += a {
uf.union(a, b)
}
}
ans := make([]bool, len(queries))
for i, q := range queries {
ans[i] = uf.find(q[0]) == uf.find(q[1])
}
return ans
}
# Accepted solution for LeetCode #1627: Graph Connectivity With Threshold
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]
// Accepted solution for LeetCode #1627: Graph Connectivity With Threshold
struct Solution;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
i
} else {
let k = self.find(j);
self.parent[i] = k;
k
}
}
fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
}
}
}
impl Solution {
fn are_connected(n: i32, threshold: i32, queries: Vec<Vec<i32>>) -> Vec<bool> {
let mut uf = UnionFind::new(n as usize);
for i in threshold + 1..n {
let mut group = vec![];
for j in 1..=n {
if j % i == 0 {
group.push((j - 1) as usize);
}
}
for w in group.windows(2) {
uf.union(w[0], w[1]);
}
}
let mut res = vec![];
for q in queries {
let a = uf.find((q[0] - 1) as usize);
let b = uf.find((q[1] - 1) as usize);
res.push(a == b)
}
res
}
}
#[test]
fn test() {
let n = 6;
let threshold = 2;
let queries = vec_vec_i32![[1, 4], [2, 5], [3, 6]];
let res = vec![false, false, true];
assert_eq!(Solution::are_connected(n, threshold, queries), res);
let n = 6;
let threshold = 0;
let queries = vec_vec_i32![[4, 5], [3, 4], [3, 2], [2, 6], [1, 3]];
let res = vec![true, true, true, true, true];
assert_eq!(Solution::are_connected(n, threshold, queries), res);
let n = 5;
let threshold = 1;
let queries = vec_vec_i32![[4, 5], [4, 5], [3, 2], [2, 3], [3, 4]];
let res = vec![false, false, false, false, false];
assert_eq!(Solution::are_connected(n, threshold, queries), res);
}
// Accepted solution for LeetCode #1627: Graph Connectivity With Threshold
class UnionFind {
p: number[];
size: number[];
constructor(n: number) {
this.p = Array(n)
.fill(0)
.map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const [pa, pb] = [this.find(a), this.find(b)];
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function areConnected(n: number, threshold: number, queries: number[][]): boolean[] {
const uf = new UnionFind(n + 1);
for (let a = threshold + 1; a <= n; ++a) {
for (let b = a * 2; b <= n; b += a) {
uf.union(a, b);
}
}
return queries.map(([a, b]) => uf.find(a) === uf.find(b));
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.