frank - 1 year ago 52
Java Question

# Get the smallest difference between elements in a data structure in less than O(n) time

Say I have some integers in a data structure. When I insert new number into the data structure,
I want to get the smallest difference between the new inserted elements and any other elements already in the data structure. What data structure and algorithm should I use? A O(n) solution is trivial and I want better.
Thanks.

One option would be to use a `TreeSet` (based on `TreeMap`), which would require several `O(lg n)` operations. The class exposes two methods which can be used to find the element which is closest to the value you wish to insert:

public E higher(E e)
Returns the least element in this set strictly greater than the given element, or null if there is no such element.

public E lower(E e)
Returns the greatest element in this set strictly less than the given element, or null if there is no such element.

``````public static int findClosest(TreeSet set, Integer val) {
if (set == null || set.size() == 0) {
return -1;
}

if (set.contains(val)) {
return 0;
}

// top == 6 for input of 7
// O(lg n) operation
Integer top = (Integer) ts.lower(val);
// bottom = 9 for input of 7
// O(lg n) operation
Integer bottom = (Integer) ts.higher(val);

if (top == null) {
return bottom - val;
}
if (bottom == null) {
return val - top;
}

return (bottom - val > val - top) ? val - top : bottom - val;
}

public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();