Graph Connectivity With Threshold - Practice Coding Problems

Graph Connectivity With Threshold - Problem

You 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:

x % z == 0
y % z == 0
z > threshold

Given the integers n and threshold, and an array of queries, determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly.

Return an array answer, where answer[i] is true if there is a path between ai and bi, or false if no path exists.

Input & Output

Example 1 — Basic Connectivity

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

› Output: [false,false,true]

💡 Note: With threshold=2, cities are connected if they share divisor > 2. City 3 and 6 share divisor 3 > 2, so they're connected. Cities 1,4 and 4,5 don't share divisors > 2.

Example 2 — Lower Threshold

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

› Output: [false,true,true]

💡 Note: With threshold=0, cities need common divisor > 0. Cities 4,6 share divisor 2 > 0 (connected). Cities 3,6 share divisor 3 > 0 (connected). Cities 4,5 share only divisor 1, which is not > 0.

Example 3 — No Connections

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

› Output: [false,false]

💡 Note: With high threshold=4, no cities can be connected since largest city is 5 and no pairs share divisor > 4.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ threshold ≤ n
1 ≤ queries.length ≤ 10⁵
queries[i].length == 2
1 ≤ a_i, b_i ≤ cities

Visualization

Tap to expand

Understanding the Visualization

Input

Cities 1-6, threshold=2, queries about connectivity

Process

Build connections where cities share divisor > 2

Output

Array of boolean answers for each query

Key Takeaway

🎯 Key Insight: Use Union-Find to precompute connected components by grouping cities that share divisors > threshold

Asked in

G Google 25 f Meta 18 a Amazon 15 M Microsoft 12

The key insight is that cities connected by common divisors form connected components that can be precomputed efficiently. The optimal approach uses Union-Find to group cities by iterating through divisors > threshold and unioning all cities divisible by each divisor. Time: O(n log n + q), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Precomputed Components	O(n log n + q)	O(n)	Build connected components once using Union-Find, then answer queries in constant time
Brute Force DFS for Each Query	O(q × n³)	O(n²)	For each query, use DFS to find if cities are connected by checking all possible paths

Union-Find with Precomputed Components — Algorithm Steps

Initialize Union-Find structure for all cities
For each divisor > threshold, union all cities divisible by it
For each query, check if cities are in same component

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each city is its own component

Union by Divisors

For each divisor > threshold, union all divisible cities

Query

Check if cities are in same component

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* parent;
    int* rank;
    int size;
} UnionFind;

UnionFind* createUF(int n) {
    UnionFind* uf = malloc(sizeof(UnionFind));
    uf->parent = malloc((n + 1) * sizeof(int));
    uf->rank = calloc(n + 1, sizeof(int));
    uf->size = n;
    
    for (int i = 0; i <= n; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    if (px == py) return;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

bool connected(UnionFind* uf, int x, int y) {
    return find(uf, x) == find(uf, y);
}

bool* solution(int n, int threshold, int queries[][2], int queryCount, int* returnSize) {
    UnionFind* uf = createUF(n);
    
    // Build connected components by iterating through divisors
    for (int z = threshold + 1; z <= n; z++) {
        int cities[1001];
        int cityCount = 0;
        for (int city = z; city <= n; city += z) {
            cities[cityCount++] = city;
        }
        
        // Union all cities divisible by z
        for (int i = 0; i < cityCount - 1; i++) {
            unionSets(uf, cities[i], cities[i + 1]);
        }
    }
    
    // Answer queries
    bool* result = malloc(queryCount * sizeof(bool));
    *returnSize = queryCount;
    for (int i = 0; i < queryCount; i++) {
        result[i] = connected(uf, queries[i][0], queries[i][1]);
    }
    
    free(uf->parent);
    free(uf->rank);
    free(uf);
    return result;
}

int main() {
    int n, threshold;
    scanf("%d", &n);
    scanf("%d", &threshold);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse queries manually
    int queries[1000][2];
    int queryCount = 0;
    
    char* ptr = line + 1; // Skip [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            queries[queryCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            queries[queryCount][1] = atoi(ptr);
            queryCount++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            if (*ptr == ',') ptr++;
        } else {
            ptr++;
        }
    }
    
    int returnSize;
    bool* result = solution(n, threshold, queries, queryCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + q)

Building components takes O(n log n) using divisor iteration, then O(1) per query with path compression

⚡ Linearithmic

Space Complexity

O(n)

Union-Find parent and rank arrays each take O(n) space

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find with Precomputed Components — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler