Problem Statement in English

You’re given a graph with n nodes numbered from 0 to n - 1.

You’re also given a 0-indexed integer array nums of length n, where if the absolute difference between the values of two nodes i and j is less than or equal to maxDiff, then there is an undirected edge between those two nodes.

It’s guaranteed that nums is sorted in non-decreasing order.

You’re also given a 2D integer array queries where each query is of the form [u, v]. For each query, you need to determine if there exists a path between nodes u and v in the graph.

Approach

Since nums is sorted, if the difference between two consecutive numbers is less than or equal to maxDiff, then they belong to the same connected component.

But if the difference is greater than maxDiff, then they belong to different connected components.

Furthermore, subsequent components are also guaranteed to not be conected to any previous components since the absolute difference between the last number of the previous component and the first number of the next component is greater than maxDiff.

If yes, then we can assign the id of the previous component. If not, we assign a number equal to the index of the previous component + 1.

So we can iterate over the nums array and assign a component number to each node. Then, for each query, we can simply check if the two nodes belong to the same component.

And we are done.

Solution in Python


class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        comp = [0] * n

        for i in range(1, n):
            if nums[i] - nums[i - 1] <= maxDiff:
                comp[i] = comp[i - 1]
            else:
                comp[i] = comp[i - 1] + 1

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

Complexity

  • Time: $O(n + q)$
    where $n$ is the number of nodes and $q$ is the number of queries.

  • Space: $O(n)$
    Since we are using an array of size $n$ to store the component information.

Mistakes I Made

I had to look this up :(

And we are done.