frank frank - 6 months ago 10
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.

Answer

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<>();
    ts.add(5);
    ts.add(1);
    ts.add(6);
    ts.add(9);
    ts.add(2);
    ts.add(3);

    int diff = findClosest(ts, 7);
    // closest is 6, so diff == 1
}