Use array scanning to identify connected segments where node differences do not exceed maxDiff. Apply a hash table to map nodes to their component IDs for O(1) path checks. Binary search helps optimize segment boundaries and quickly answer multiple path queries efficiently.
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.
How GhostInterview Helps
- Automatically detects connected segments and assigns component IDs for fast query resolution.
- Highlights failure modes when nodes are incorrectly assumed disconnected due to array gaps.
- Provides step-by-step explanation of segment mapping and hash lookup logic to clarify answer reasoning.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Path Existence Queries in a Graph I instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Path Existence Queries in a Graph I from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the number of connected components in an undirected graph formed by properties arrays, using array scanning and hash lookup techniques.
Open problem page#3607 Power Grid MaintenanceDetermine which power stations remain connected after maintenance using array scanning and hash lookups to track components efficiently.
Open problem page#3534 Path Existence Queries in a Graph IISolve path existence queries in a graph using binary search on the answer space, focusing on sorted nodes and maximum difference.
Open problem page