Google Interview Question - connected components given sorted array

google-graph-connected-components-sorted-array.py

"""
https://leetcode.com/discuss/post/6686960/google-swe2-phone-screen-rejected-by-ano-ek6t/

📌 Company: Google
📍 Round: Phone Screen
🧠 Role: SDE-2
🗓️ Experience: 2 YOE

🧪 Question: Graph Connectivity via Value Proximity
Prompt: Given a sorted array arr of size N, and an integer diff, 
construct an undirected graph where each node represents an index. 
Connect nodes i and j if |arr[i] - arr[j]| <= diff.

You are given a list of queries [u, v]. Return a list of booleans 
indicating whether there is a path between u and v.

Example:

arr = [1, 2, 3, 6]
diff = 2
queries = [[0, 2], [1, 3]]

Output: [True, False]


"""
# time:O(n+Q), space:O(n)

def isConnected(arr,diff,queries):
	n = len(arr)
	components = [0] * n
	comp_ID = 0

	# 1 - build graph
	for i in range(1, n):
		if arr[i] - arr[i-1] <= diff:
			components[i] = comp_ID
		else:
			comp_ID += 1
			components[i] = comp_ID


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



arr = [1, 2, 3, 6]
diff = 2
queries = [[0, 2], [1, 3]]
print(isConnected(arr, diff, queries)) #[True, False]



arr = [1, 3, 4, 6]
diff = 2
queries = [[0, 2], [1, 3]]
print(isConnected(arr, diff, queries)) #[True, True]