Path Existence Queries in a Graph I

Path Existence Queries in a Graph I

What is this problem about?

The Path Existence Queries in a Graph I problem gives you an array of node values and a maximum edge-weight difference maxDiff. Two nodes u and v are connected if |vals[u] - vals[v]| <= maxDiff. For each query (u, v), determine if there's a path between u and v in this implicit graph. This coding problem uses Union-Find after sorting nodes by value. The array, union find, hash table, graph, and binary search interview pattern is the core.

Why is this asked in interviews?

Google asks this because the key insight — sorting by value and only connecting consecutive elements within maxDiff creates the same connectivity as the full graph — allows efficient Union-Find construction. This reduces the O(n²) edge generation to O(n log n).

Algorithmic pattern used

Sort + Union-Find. Sort nodes by value (keeping original indices). For each consecutive pair in sorted order: if vals[sorted[i+1]] - vals[sorted[i]] <= maxDiff, union them. After processing, answer each query (u,v): return find(u) == find(v).

The key insight: if sorted values form a chain where each adjacent pair is within maxDiff, transitivity ensures all connected through the chain.

Example explanation

vals=[5,1,3,7,4], maxDiff=2. Sort: [(1,1),(3,2),(4,4),(5,0),(7,3)].

• 3-1=2 ≤ 2: union(1,2). 4-3=1 ≤ 2: union(2,4). 5-4=1 ≤ 2: union(4,0). 7-5=2 ≤ 2: union(0,3). All connected. Query(1,3): find(1)==find(3)→ true.

Common mistakes candidates make

• Building the full graph with all O(n²) edges (too slow).
• Not sorting by value before connecting (must connect by proximity).
• Not using the index map after sorting (need to track original indices).
• Not applying path compression in Union-Find.

Interview preparation tip

Path existence in proximity graphs (connect within distance d) always uses sort+Union-Find. The critical insight: if you sort by value, only consecutive pairs within maxDiff need to be connected — transitivity handles the rest. This reduces O(n²) to O(n log n). Practice similar "connect nodes within distance" problems: k-nearest neighbors, range graphs, geographic proximity.