Connected Components in a Graph II

LeetCode Problem 3532 is an interesting one that tests understanding of graph theory and connected components.

The problem gives us:

• An integer n representing nodes in a graph (labeled 0 to n-1)
• An array nums of length n in non-decreasing order
• A value maxDiff
• A series of queries asking if a path exists between two nodes

Two nodes i and j have an edge between them if |nums[i] - nums[j]| <= maxDiff. For each query [u, v], we need to determine if there's a path from node u to node v.

The Key Insight: Connected Components

This problem is essentially asking to determine if two nodes belong to the same connected component in an undirected graph.

What makes this problem particularly approachable is that there's no need to perform a BFS or DFS for each query. Since nums is already sorted, this property can be exploited to pre-compute all connected components in linear time!

public bool[] PathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries)
{
    int[] vertexToConnectedComponent = new int[nums.Length];
    int currentConnectedComponent = 1;
    vertexToConnectedComponent[0] = currentConnectedComponent;
    for (int i = 1; i < nums.Length; i++)
    {
        if (nums[i] - nums[i - 1] > maxDiff) currentConnectedComponent++;
        vertexToConnectedComponent[i] = currentConnectedComponent;
    }
    bool[] retVal = new bool[queries.Length];
    for (int i = 0; i < queries.Length; i++)
        retVal[i] = vertexToConnectedComponent[queries[i][0]] == vertexToConnectedComponent[queries[i][1]];
    return retVal;
}

Breaking Down the Solution

1. I create an array vertexToConnectedComponent to map each vertex to its connected component ID
2. Starting with component ID 1, I assign the first vertex to this component
3. Then, I iterate through the remaining vertices:
   • If the difference between the current element and the previous exceeds maxDiff, I start a new component
   • Otherwise, the current vertex belongs to the same component as the previous one
4. Finally, I process each query by simply checking if both nodes belong to the same component

Why This Works

The key insight is that because nums is sorted, only adjacent values need to be checked to determine component boundaries. Any vertex can only connect to other vertices whose values are within maxDiff of its own value.

Since the array is sorted, if vertex i cannot connect to vertex i+1 (because their difference exceeds maxDiff), then vertex i certainly cannot connect to any vertex j where j > i+1, as those values would be even larger.

This property allows for identification of connected components with a single pass through the array!

Time and Space Complexity

• Time Complexity: O(n + q) where n is the number of nodes and q is the number of queries
• Space Complexity: O(n) for the component mapping array

Conclusion

This problem illustrates how understanding the unique properties of input data can lead to elegant, efficient solutions. By recognizing that the sorted nature of nums allows for calculating connected components in a single pass, the need for more complex graph traversal algorithms is avoided.

It's no surprise, then, that this solution performs well against other submissions on LeetCode. Sometimes, the most elegant solutions come from finding and exploiting these special properties rather than applying generic algorithms.

You can find the complete solution code above. Cheers, ACC