Problem Description

You have a graph with n nodes labeled from 0 to n - 1. You're given:

• An integer array nums of length n that is sorted in non-decreasing order
• An integer maxDiff that determines which nodes can be connected

The graph's edges are formed based on a simple rule: an undirected edge exists between nodes i and j if and only if the absolute difference between their corresponding values in nums is at most maxDiff. In other words, nodes i and j are connected if |nums[i] - nums[j]| <= maxDiff.

You're also given a 2D array queries where each query queries[i] = [ui, vi] asks whether there exists a path between nodes ui and vi in the graph.

Your task is to return a boolean array answer where answer[i] is true if there's a path between nodes ui and vi for the i-th query, and false otherwise.

The key insight here is that since nums is sorted in non-decreasing order, nodes can only form connected components with consecutive indices. If the difference between consecutive elements in nums exceeds maxDiff, those nodes will be in different connected components. The solution cleverly tracks which connected component each node belongs to by checking gaps in the sorted array - whenever nums[i] - nums[i-1] > maxDiff, a new connected component starts. Then, for each query, it simply checks if both nodes belong to the same connected component.

Intuition

Let's think about what edges can exist in this graph. Since nums is sorted, we have nums[0] <= nums[1] <= nums[2] <= ... <= nums[n-1].

For any two nodes i and j where i < j, we know that nums[j] >= nums[i], so the absolute difference is simply nums[j] - nums[i].

Now, here's the crucial observation: if node i can connect to node j (where i < j), then node i can also connect to all nodes between i and j. Why? Because for any node k where i < k < j, we have nums[i] <= nums[k] <= nums[j], which means nums[k] - nums[i] <= nums[j] - nums[i] <= maxDiff.

This means that connected components must consist of consecutive indices. A connected component can't "skip" nodes - if nodes i and j are in the same component, then all nodes between them must also be in that component.

So when does a connected component end and a new one begin? It happens when we find a gap that's too large. Specifically, if we're looking at consecutive nodes i-1 and i, and nums[i] - nums[i-1] > maxDiff, then node i cannot connect to node i-1. Since connected components must be consecutive, this means node i starts a new connected component.

This leads us to a simple solution: we can scan through the array once and mark which connected component each node belongs to. We start with component 0, and whenever we find a gap larger than maxDiff between consecutive elements, we increment the component counter. Then, to check if two nodes are connected, we just check if they belong to the same component - a constant time operation!

Learn more about Union Find, Graph and Binary Search patterns.

Solution Approach

The implementation uses a grouping strategy to efficiently determine connectivity between nodes.

Data Structure:

• Array g of size n: Stores the connected component index for each node
• Variable cnt: Tracks the current connected component index, starting from 0

Algorithm Steps:

1. Initialize the grouping array: Create an array g where g[i] will store which connected component node i belongs to. Set g[0] = 0 since the first node belongs to component 0.

2. Identify connected components: Iterate through the sorted nums array from index 1 to n-1:

   • For each node i, check if nums[i] - nums[i-1] > maxDiff
   • If true, this indicates a "break" in connectivity - node i cannot connect to node i-1
   • When a break is found, increment cnt to start a new connected component
   • Assign g[i] = cnt to mark which component node i belongs to

3. Process queries: For each query [u, v]:

   • Simply check if g[u] == g[v]
   • If they're equal, nodes u and v are in the same connected component, so return true
   • Otherwise, return false

Example walkthrough: If nums = [1, 3, 4, 8, 9] and maxDiff = 2:

• Node 0 (value 1): g[0] = 0 (component 0)
• Node 1 (value 3): 3 - 1 = 2 <= 2, so g[1] = 0 (same component)
• Node 2 (value 4): 4 - 3 = 1 <= 2, so g[2] = 0 (same component)
• Node 3 (value 8): 8 - 4 = 4 > 2, so increment cnt to 1, g[3] = 1 (new component)
• Node 4 (value 9): 9 - 8 = 1 <= 2, so g[4] = 1 (same component as node 3)

Result: g = [0, 0, 0, 1, 1], meaning nodes 0, 1, 2 form one component and nodes 3, 4 form another.

Time Complexity: O(n + q) where q is the number of queries Space Complexity: O(n) for the grouping array

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• nums = [2, 5, 6, 10, 15]
• maxDiff = 3
• queries = [[0, 2], [1, 4], [3, 4]]

Step 1: Build the connected components array g

We'll track which component each node belongs to by checking gaps between consecutive elements:

• Node 0 (value 2): First node always starts component 0

  • g[0] = 0, cnt = 0

• Node 1 (value 5): Check gap from previous

  • Gap: 5 - 2 = 3 ≤ 3 ✓ (within maxDiff)
  • g[1] = 0 (same component)

• Node 2 (value 6): Check gap from previous

  • Gap: 6 - 5 = 1 ≤ 3 ✓ (within maxDiff)
  • g[2] = 0 (same component)

• Node 3 (value 10): Check gap from previous

  • Gap: 10 - 6 = 4 > 3 ✗ (exceeds maxDiff)
  • Start new component: cnt = 1
  • g[3] = 1 (new component)

• Node 4 (value 15): Check gap from previous

  • Gap: 15 - 10 = 5 > 3 ✗ (exceeds maxDiff)
  • Start new component: cnt = 2
  • g[4] = 2 (new component)

Result: g = [0, 0, 0, 1, 2]

This means:

• Component 0: nodes {0, 1, 2} with values {2, 5, 6}
• Component 1: node {3} with value {10}
• Component 2: node {4} with value {15}

Step 2: Process queries

Now we can answer each query in O(1) time:

• Query [0, 2]: Check if g[0] == g[2]

  • g[0] = 0 and g[2] = 0 → Same component → true

• Query [1, 4]: Check if g[1] == g[4]

  • g[1] = 0 and g[4] = 2 → Different components → false

• Query [3, 4]: Check if g[3] == g[4]

  • g[3] = 1 and g[4] = 2 → Different components → false

Final Answer: [true, false, false]

The beauty of this approach is that we only need one pass through the array to identify all connected components, then each query is answered by a simple array lookup comparison.

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n + q), where n is the length of the nums array and q is the number of queries.

• The first loop iterates through the array once from index 1 to n-1, performing constant-time operations (comparison and assignment) at each step, which takes O(n) time.
• The list comprehension for processing queries iterates through all queries and performs constant-time array lookups and comparisons for each query, which takes O(q) time.
• Overall time complexity: O(n + q)

The space complexity is O(n), where n is the length of the nums array.

• The array g of size n is created to store the cumulative count values, requiring O(n) space.
• The variable cnt uses constant space O(1).
• The output list storing boolean results has length equal to the number of queries, but this is typically considered part of the output rather than auxiliary space.
• Overall space complexity: O(n)

Note: The reference answer states O(n) for time complexity, which appears to assume that the number of queries q is bounded by n or not considered as a separate parameter in the complexity analysis.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Graph Construction

A common misconception is thinking that the graph edges are only between consecutive indices in the sorted array. The problem states that an edge exists between ANY two nodes i and j where |nums[i] - nums[j]| <= maxDiff, not just consecutive ones.

Why the solution still works: Even though edges can exist between non-consecutive nodes, the sorted nature of nums creates a transitive property. If node i can connect to node j, and node j can connect to node k, then all three belong to the same component. The gap-checking approach correctly identifies when this transitivity breaks.

2. Incorrect Handling of Edge Cases

Developers might forget to handle:

• Single element array (n = 1)
• All elements being identical
• maxDiff = 0 (only identical values can connect)

Solution: The current implementation handles these cases correctly:

# For n = 1, the loop doesn't execute, g[0] = 0
# For identical elements, nums[i] - nums[i-1] = 0 <= maxDiff always
# For maxDiff = 0, only consecutive identical values stay in same component

3. Off-by-One Errors in Component Assignment

A subtle bug could occur if incrementing the component counter at the wrong time:

Incorrect approach:

# Wrong: Incrementing before assignment
for i in range(1, n):
    if nums[i] - nums[i - 1] > maxDiff:
        current_group += 1
        group_id[i] = current_group  # Bug: should assign after increment check
    else:
        group_id[i] = current_group

Correct approach (as in solution):

for i in range(1, n):
    if nums[i] - nums[i - 1] > maxDiff:
        current_group += 1
    group_id[i] = current_group  # Assigns correctly whether incremented or not

4. Assuming Unsorted Input

If someone mistakenly assumes nums might be unsorted and tries to sort it first:

Wrong:

sorted_nums = sorted(nums)  # Don't do this!
# This breaks the index correspondence between nodes and their values

The problem explicitly states nums is already sorted, and the indices in queries refer to the original positions in nums.

5. Using Union-Find When Unnecessary

Some might overcomplicate by implementing Union-Find:

# Overly complex for this problem
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    # ... union and find methods

While Union-Find would work, it's overkill here. The sorted nature of nums allows the simpler linear scan approach with O(n) time and space complexity.