Find two elements with smallest absolute difference in an interval

Question

I'm given an array and a list of queries of type L R which mean find the smallest absolute difference between any two array elements such that their indices are between L and R inclusive (Here the starting index of array is at 1 instead of at 0)

For example take the array a with elements 2 1 8 5 11 then the query 1-3 which would be (2 1 8) the answer would be 1=2-1, or the query 2-4 (1 8 5) where the answer would be 3=8-5

Now this is easy if you have to look at one interval you sort the interval and then compare i-th element with i+1-th and store the minimum difference for each i.

The problem is that I'll have a lot of intervals to check I have to keep the original array intact.

What I've done is I constructed a new array b with indices from the first one such that a[b[i]] <= a[b[j]] for i <= j. Now for each query I loop through the whole array and look if b[j] is between L and R if it is compare its absolute difference to the first next element that is also between L and R keep the minimum and then do the same for that element until you get to the end.

This is inefficient because for each query I have to check all elements of the array especially if the query is small compared to the size of array. I'm looking for a time efficient approach.

EDIT: The numbers don't have to be consecutive, perhaps I gave a bad array as an example, What I've meant for example if it's 1 5 2 then the smallest difference is 1=2-1. In a sorted array the smallest difference is guaranteed to be between two consecutive elements, that's why I've thought of sorting

Answer 1

I'll sketch an O(n (√n) log n)-time solution, which might be fast enough? When I gave up sport programming, computers were a lot slower.

The high-level idea is to apply Mo's trick to a data structure with the following operations.

insert(x) - inserts x into the underlying multiset
delete(x) - deletes one copy of x from the underlying multiset
min-abs-diff() - returns the minimum absolute difference
                 between two elements of the multiset
                 (0 if some element has multiplicity >1)

Read in all of the query intervals [l, r], sort them in order of lexicographically nondecreasing (floor(l / sqrt(n)), r) where n is the length of the input, and then to process an interval I, insert the elements in I - I' where I' was the previous interval, delete the elements in I' - I, and report the minimum absolute difference. (The point of the funny sort order is to reduce the number of operations from O(n^2) to O(n √n) assuming n queries.)

There are a couple ways to implement the data structure to have O(log n)-time operations. I'm going to use a binary search tree for clarity of exposition, but you could also sort the array and use a segment tree (less work if you don't have a BST implementation that lets you specify decorations).

Add three fields to each BST node: min (minimum value in the subtree rooted at this node), max (maximum value in the subtree rooted at this node), min-abs-diff (minimum absolute difference between values in the subtree rooted at this node). These fields can be computed bottom-up like so.

if node v has left child u and right child w:
    v.min = u.min
    v.max = w.max
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max,
                         w.min - v.value, w.min-abs-diff)

if node v has left child u and no right child:
    v.min = u.min
    v.max = v.value
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)

if node v has no left child and right child w:
    v.min = v.value
    v.max = w.max
    v.min-abs-diff = min(w.min - v.value, w.min-abs-diff)

if node v has no left child and no right child:
    v.min = v.value
    v.max = v.value
    v.min-abs-diff = ∞

This logic can be implemented pretty compactly.

if v has a left child u:
    v.min = u.min
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)
else:
    v.min = v.value
    v.min-abs-diff = ∞
if v has a right child w:
    v.max = w.max
    v.min-abs-diff = min(v.min-abs-diff, w.min - v.value, w.min-abs-diff)
else:
    v.max = v.value

insert and delete work as usual, except that the decorations need to be updated along the traversal path. The total time is still O(log n) for reasonable container choices.

min-abs-diff is implemented by returning root.min-abs-diff where root is the root of the tree.