Problem Description

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1. You also receive an integer array nums of length n sorted in non-decreasing order, 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). Additionally, you are provided with a 2D integer array queries. For each queries[i] = [u_i, v_i], you must determine whether there exists a path between nodes u_i and v_i. The objective is to return a boolean array answer, where answer[i] is true if there exists a path between u_i and v_i for the i-th query, and false otherwise.

Intuition

To solve this problem, we need to understand how nodes are connected. Given that nums is sorted and a connection (an edge) between nodes exists if their values' absolute difference is within maxDiff, the nodes can be divided into separate connected components. These components are contiguous segments of nodes connected directly or indirectly where each node in a segment can reach any other node within the same segment.

To achieve this grouping, we process nums from start to finish, initializing an array g that tracks the component index for each node. Starting from index 1, for each node, if the difference between this node and the previous one exceeds maxDiff, they belong to different components. Thus, we increment a component counter cnt. We assign this counter as the component identifier for each node.

Subsequently, when processing each query, we can simply check if the nodes u and v belong to the same component by comparing their values in g. If they have the same component index, they are connected, and the answer is true. Otherwise, it is false.

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

Solution Approach

In this solution, we use an approach called "Grouping." The main idea is to determine which nodes are part of the same connected component by looking at the differences between consecutive elements in the array nums.

1. Initialization: We start by initializing an array g of size n with all elements set to 0. This array will track the component index for each node. We also initialize a counter cnt to 0, which keeps track of the current component index.

2. Grouping Nodes: We iterate through nums starting from index 1. For each node i, we check the difference between nums[i] and nums[i-1]. If this difference is greater than maxDiff, it implies that node i starts a new connected component from the previous node. When this condition holds, we increment the cnt by 1 to denote a new component beginning. We then assign this cnt value to g[i] to mark that node i belongs to this component.

   for i in range(1, n):
       if nums[i] - nums[i - 1] > maxDiff:
           cnt += 1
       g[i] = cnt

3. Answering Queries: For each query [u, v] from the queries array, we simply check if g[u] is equal to g[v]. If they are equal, it means nodes u and v are in the same connected component, and we return true for this query. If not, we return false.

   return [g[u] == g[v] for u, v in queries]

The algorithm effectively uses the sorted nature of nums and the fixed maxDiff threshold to determine connectivity, leading to a time complexity of O(n) for processing the nums and O(m) for answering the queries where m is the number of queries.

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Suppose we have:

• n = 5, which means there are 5 nodes labeled from 0 to 4.
• nums = [1, 3, 4, 8, 9], which is a sorted array.
• maxDiff = 2, meaning an edge exists between nodes if the absolute difference between their values is at most 2.
• queries = [[0, 2], [0, 3], [3, 4]].

Step 1: Initialization

We begin by initializing an array g of size n with zeros: g = [0, 0, 0, 0, 0]. We also initialize our component counter cnt to 0.

Step 2: Grouping Nodes

Now, we iterate through the nums array starting from index 1.

• At index 1: nums[1] - nums[0] = 3 - 1 = 2 which is less than or equal to maxDiff. Thus, node 1 is in the same component as node 0: g = [0, 0, 0, 0, 0].

• At index 2: nums[2] - nums[1] = 4 - 3 = 1 which is less than or equal to maxDiff. Thus, node 2 is in the same component: g = [0, 0, 0, 0, 0].

• At index 3: nums[3] - nums[2] = 8 - 4 = 4 which is greater than maxDiff. Hence, node 3 starts a new component. Increment cnt to 1: g = [0, 0, 0, 1, 0].

• At index 4: nums[4] - nums[3] = 9 - 8 = 1 which is less than or equal to maxDiff. Thus, node 4 is in the same component as node 3: g = [0, 0, 0, 1, 1].

Step 3: Answering Queries

Lastly, we address each query:

• Query [0, 2]: Nodes 0 and 2 are in the same component since g[0] == g[2], so return true.

• Query [0, 3]: Nodes 0 and 3 are in different components because g[0] != g[3], resulting in false.

• Query [3, 4]: Nodes 3 and 4 are in the same component since g[3] == g[4], so return true.

Final Answer

The boolean array reflecting the answers to the queries is [true, false, true].

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n). This is because the code involves a single loop that iterates over the nums array once to compute the g array, where n is the length of the nums array. Each iteration involves simple arithmetic operations and comparisons that take constant time.

The space complexity is O(n), as an additional array g of size n is used to store cumulative counts based on the difference condition. Other space uses are negligible compared to the g array.

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