#3532

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Path Existence Queries in a Graph I

Determine if paths exist between nodes using array scanning and hash lookups for efficient component checks in graphs.

array hash table binary search union find graph

Problem Statement

You are given an integer n representing the number of nodes labeled from 0 to n-1, an array nums sorted in non-decreasing order, and an integer maxDiff. A graph is defined where nodes i and j are connected if |nums[i] - nums[j]| <= maxDiff.

Given a list of queries where each query consists of two nodes, return a boolean array indicating whether a path exists between the two nodes in each query. Each query requires checking connectivity across potentially multiple segments formed by array values constrained by maxDiff.

Examples

Example 1

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

Output: [true,false]

Example 2

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

Output: [false,false,true,true]

The resulting graph is:

Constraints

1 <= n == nums.length <= 105
0 <= nums[i] <= 105
nums is sorted in non-decreasing order.
0 <= maxDiff <= 105
1 <= queries.length <= 105
queries[i] == [ui, vi]
0 <= ui, vi < n

Solution Approach

Identify Connected Segments

Scan nums sequentially to group nodes into continuous segments where differences between consecutive values do not exceed maxDiff. Each segment represents a connected component.

Map Nodes to Components Using Hash Table

Create a hash table that assigns each node to its segment ID. This allows quick O(1) lookup during query checks and avoids repeated traversal of the graph.

Answer Queries Efficiently

For each query, compare the component IDs of the two nodes. If they share the same ID, a path exists; otherwise, no path exists. Use binary search to refine segment boundaries for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + q) for scanning and query lookup, with n being array length and q being number of queries. Space complexity is O(n) to store component IDs in the hash table.

What Interviewers Usually Probe

Look for continuous segments in nums where differences are within maxDiff.
Consider mapping nodes to components instead of exploring the graph for each query.
Check if queries access the same or different segments efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to account for multiple consecutive nodes forming a segment.
Using repeated graph traversal per query instead of precomputed components.
Not handling edge cases where maxDiff is zero or very large correctly.

Follow-up variants

Allow dynamic updates to nums and handle incremental queries.
Find the minimum maxDiff required to connect two given nodes.
Support weighted edges where difference contributes to edge cost and queries check reachability within a threshold.

FAQ

What is the main approach for Path Existence Queries in a Graph I?

The problem is solved by grouping nodes into connected segments using array scanning, then using a hash table to map nodes to component IDs for fast query checks.

Can I use union-find for this problem?

Yes, union-find works, but for sorted arrays, array scanning with hash lookup is faster and simpler due to continuous segments.

How do I handle large queries efficiently?

Precompute component IDs for all nodes and use hash table lookups to answer each query in O(1) time.

What happens if maxDiff is zero?

Only nodes with identical nums values form segments, so connectivity is limited to repeated values.

Does sorting nums help in this problem?

Yes, sorted nums allows sequential scanning to detect segments and apply binary search to efficiently define component boundaries.

terminal

Solution

Solution 1: Grouping

According to the problem description, the node indices within the same connected component must be consecutive. Therefore, we can use an array $g$ to record the connected component index for each node and a variable $\textit{cnt}$ to track the current connected component index. As we iterate through the $\textit{nums}$ array, if the difference between the current node and the previous node is greater than $\textit{maxDiff}$, it indicates that the current node and the previous node are not in the same connected component. In this case, we increment $\textit{cnt}$. Then, we assign the current node's connected component index to $\textit{cnt}$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def pathExistenceQueries(
        self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]
    ) -> List[bool]:
        g = [0] * n
        cnt = 0
        for i in range(1, n):
            if nums[i] - nums[i - 1] > maxDiff:
                cnt += 1
            g[i] = cnt
        return [g[u] == g[v] for u, v in queries]

Continue Practicing

#3493 properties graph #3607 power grid maintenance #3534 path existence queries in a graph ii