Find if any pair exists in an unsorted array?

Question

I have come across a programming question in which I have to determine :

Does there exists at least one pair in a given unsorted array such that

|i - j| <= K and |A[i] - A[j]| <= x ?

For example:

A = {5,4,8,3} and x = 3 and k = 2.

Answer: Yes - any one of (5,4), (5,8), (4,3)

I have tried it many times but couldn't think of any algorithm with time complexity less than O(nk). I have also tried Balanced Binary search tree but it is not helping me.

• paparazzo: Yes I think it is nk
• CodesInChaos: You can simply sort the array at cost O(n log n) and then proceed with solution for sorted arrays at cost O(n).
• gnasher729: Sorting destroys the relationship between indices, which are required to be close together.
• Ewan: sounds like a variation of the subset pum problem en.wikipedia.org/wiki/Subset_sum_problem

Answer 1

This can be done in O(nlogk) using a balanced search tree, in which for every node you also store MIN(node) - the minimum value in its subtree, MAX(node) - the maximum value in its subtree and DIST(node) - the minimum absolute difference of any pair of values in its subtree. These values can be calculated recursively using the following equations:

MAX(node) = max{node->value, MAX(node->left), MAX(node->right)}
MIN(node) = min{node->value, MIN(node->left), MIN(node->right)}
DIST(node) = min{DIST(node->left), DIST(node->right),
 |MAX(node->left) - (node->value)|,
 |MIN(node->right) - (node->value)|}

You can update those values in O(log k) when updating the tree since you only need to update them on the search path.

Then you can slide a window of size k on the array and check if it contains the required pair using the tree as follows:

1. Put the first k elements (0..k-1) of the array in the tree described above and set i=k.
2. If DIST(root node) <= X, return True.
3. If i>= n, return False.
4. Remove the (i-k)-th element of the array from the tree, add the i-th element of the array to the tree (while updating MIN, MAX and DIST of the nodes on the insert/remove pathes).
5. Increase i by one and go to 2.

Step 1 (building the tree) takes O(nlogk) and step 4 (updating the tree) takes O(log k) and is repeated O(n) times.

Answer 2

It can be done in linear expected time.

Keep an hashtable H mapping buckets of the form [i*k, (i + 1)*k] to an integer falling in that range. Then:

H = HashTable();
for (i = 0; i < len(A); ++i) {
 bucket = A[i] / x;
 if (H.contains(bucket)) {
 return true; // Two elements in same bucket -> pair exists
 }
 if (H.contains(bucket - 1) && (A[i] - H[bucket - 1]) < x) {
 return true; // Element in previous bucket with right distance
 }
 if (H.contains(bucket + 1) && (H[bucket + 1] - A[i]) < x) {
 return true; // Element in next bucket with right distance
 }
 // Time to update H
 H[bucket] = A[i];
 if (i >= K) {
 H.remove(A[i - K] / x); // Remove old entry from H
 }
}
return false; // No pair found

Answer 3

I think you can up to nlog(k). Think about it in geometry. For each dot you draw a tunnel of forward values matching the criteria. Then for the next dot you check previous tunnels. If you sort your tunnels somehow you should be able to make the check without iterating all of them.