Skip to main content
Talentd

Path Existence Queries in a Graph II - Solution & Explanation

HardArrayTwo PointersBinary SearchDynamic Programming15 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.

You are also given an integer array nums of length n and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., |nums[i] - nums[j]| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [ui, vi], find the minimum distance between nodes ui and vi. If no path exists between the two nodes, return -1 for that query.

Return an array answer, where answer[i] is the result of the ith query.

Note: The edges between the nodes are unweighted.

 

Example 1:

Input: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]

Output: [1,1]

Explanation:

The resulting graph is:

Query Shortest Path Minimum Distance
[0, 3] 0 → 3 1
[2, 4] 2 → 4 1

Thus, the output is [1, 1].

Example 2:

Input: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]

Output: [1,2,-1,1]

Explanation:

The resulting graph is:

Query Shortest Path Minimum Distance
[0, 1] 0 → 1 1
[0, 2] 0 → 1 → 2 2
[2, 3] None -1
[4, 3] 3 → 4 1

Thus, the output is [1, 2, -1, 1].

Example 3:

Input: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]

Output: [0,-1,-1]

Explanation:

There are no edges between any two nodes because:

  • Nodes 0 and 1: |nums[0] - nums[1]| = |3 - 6| = 3 > 1
  • Nodes 0 and 2: |nums[0] - nums[2]| = |3 - 1| = 2 > 1
  • Nodes 1 and 2: |nums[1] - nums[2]| = |6 - 1| = 5 > 1

Thus, no node can reach any other node, and the output is [0, -1, -1].

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 105
  • 0 <= maxDiff <= 105
  • 1 <= queries.length <= 105
  • queries[i] == [ui, vi]
  • 0 <= ui, vi < n

Approach Overview

Problem Overview: You are given a graph and multiple queries asking whether a valid path exists between two nodes under specific constraints (typically edge limits or conditions). Instead of recomputing connectivity for every query independently, the challenge is to process queries efficiently while the graph structure stays fixed.

Approach 1: BFS/DFS Per Query (Brute Force) (Time: O(Q * (V + E)), Space: O(V))

The most direct method is to treat every query independently. For each query, run a BFS or DFS starting from the source node and check if the destination node can be reached while respecting the constraint. During traversal, ignore edges that violate the query condition. This approach is simple and easy to implement using adjacency lists. However, it quickly becomes inefficient when the number of queries is large because the entire graph may be traversed for each query.

Approach 2: Offline Queries with Sorting + Union-Find (Optimal) (Time: O((E + Q) log E), Space: O(V))

A more scalable approach processes queries offline. First, sort all edges based on the constraint parameter (commonly weight or limit). Sort queries by the same constraint value. As you iterate through queries in increasing order, incrementally add valid edges to a Union-Find structure. Each union operation connects components whose edges satisfy the current query constraint. When processing a query, simply check whether the two nodes belong to the same connected component using find(). This transforms repeated graph traversals into near-constant time connectivity checks.

The key insight: connectivity only changes when new edges become eligible. By sorting both edges and queries, you add edges exactly once and reuse the resulting components for later queries. Union-Find with path compression and union by rank keeps operations extremely fast in practice.

Approach 3: Binary Search + Connectivity Checks (Time: O(Q log E * α(V)), Space: O(V))

Another variation applies binary search on the sorted edge list to determine the maximum prefix of edges that satisfy each query. For every candidate prefix, use a Union-Find structure to test connectivity. While this method demonstrates how monotonic constraints enable binary search, it tends to rebuild connectivity structures multiple times, making it slower than the fully offline approach.

These techniques rely heavily on efficient graph representations and the sorting of edges and queries. The Union-Find data structure is the central optimization because it answers connectivity queries in almost constant time.

Recommended for interviews: The offline sorting + Union-Find approach is what most interviewers expect for hard connectivity query problems. Showing the brute-force BFS/DFS solution first demonstrates understanding of the graph traversal baseline. Transitioning to Union-Find with sorted edges proves you can optimize repeated connectivity queries and reason about algorithmic scaling.

Solution

Key observation: an edge exists between two nodes if the absolute difference of their values is at most maxDiff. After sorting nodes by value, greedily jumping from a smaller-value node to the largest reachable value at each step yields the shortest path.

The preprocessing steps are as follows:

  1. Sort (nums[i], i) pairs by value;
  2. Use two pointers: for each sorted position l, find the rightmost position r such that pairs[r].first - pairs[l].first <= maxDiff. Set f[i][0] = j, meaning from node i, one jump reaches node j, the largest-value node within maxDiff;
  3. Build a binary lifting table f[i][k], representing the node reached after 2^k jumps from node i.

For each query, assume nums[u] <= nums[v]:

  • If u == v, the answer is 0;
  • If nums[u] == nums[v], the answer is 1;
  • Otherwise, use binary lifting to find the minimum number of jumps so that the reached node's value is at least nums[v]; if unreachable, return -1, otherwise the answer is d + 1.

The time complexity is O(n log n + (n + q) log n) and the space complexity is O(n log n), where n is the number of nodes and q is the number of queries.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS/DFS per QueryO(Q * (V + E))O(V)Small graphs or very few queries where repeated traversal cost is acceptable
Offline Sorting + Union-FindO((E + Q) log E)O(V)Best general solution when many connectivity queries must be processed efficiently
Binary Search + DSU RebuildO(Q log E * α(V))O(V)Useful when query constraints are monotonic and binary search logic is easier to reason about

Video Solution

Path Existence Queries in a Graph II | Leetcode 3534 | Binary Lifting | Concepts & Questions - 5 • codestorywithMIK • 8,491 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Path Existence Queries in a Graph II easy or hard?
This problem is considered hard because it combines graph connectivity, offline query processing, sorting, and Union-Find optimizations. The main challenge is recognizing that repeated path searches can be replaced with incremental connectivity tracking.
Path Existence Queries in a Graph II Python/Java solution
Typical implementations use Union-Find with path compression. Python, Java, C++, and Go solutions all follow the same pattern: sort edges and queries, union eligible edges while iterating, and answer each query using DSU find operations.
What is the best approach for Path Existence Queries in a Graph II?
The most efficient approach is processing queries offline using sorting and a Union-Find (Disjoint Set Union) structure. Sort edges by constraint (such as weight) and sort queries by the same parameter. Incrementally union valid edges and answer each query with a connectivity check. This avoids repeated graph traversals and keeps each query near constant time.
How to solve Path Existence Queries in a Graph II in O((E+Q) log E)?
Sort edges by the constraint value and sort queries by their allowed limit. Iterate through queries while progressively adding edges that satisfy the limit into a Union-Find structure. For each query, check whether the two nodes belong to the same connected component. This eliminates repeated BFS or DFS traversals.
Is Path Existence Queries in a Graph II asked at Google/Amazon/Meta?
Connectivity query problems using Union-Find and offline sorting frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variations often involve edge weight limits, dynamic connectivity, or constraint-based path validation.
What data structure is used in Path Existence Queries in a Graph II?
The core data structure is Union-Find (Disjoint Set Union). It efficiently maintains connected components while edges are added. The solution also relies on sorted arrays for edges and queries, along with adjacency or edge lists for the graph representation.
What is the time complexity of Path Existence Queries in a Graph II?
The optimal Union-Find based solution runs in O((E + Q) log E) time due to sorting edges and queries. Each union and find operation is nearly O(1) with path compression and union by rank. Space complexity is O(V) for the DSU structure and adjacency representation.

Ready to solve this problem?

Practice Path Existence Queries in a Graph II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays