Efficient search for not empty intersection (Java)

Question

I have a method that returns an integer value or integer range (initial..final) and I want to know if values are all disjoint.

Is there a more efficient solution than the following one:

ArrayList<Integer> list = new ArrayList<Integer>();

// For single value
int value;
if(!list.contains(value))
    list.add(value);
else
    error("",null);

// Range
int initialValue,finalValue;
for(int i = initialValue; i <= finalValue; i++){
    if(!list.contains(i))
        list.add(i);
    else
        error("",null);
}

Answer 1

Finding a value (contains) in HashSet is a constant-time operation (O(1)) on average, which is better than a List, where contains is linear (O(n)). So, if your lists are large enough, it may be worthwhile to replace your first line with:

HashSet<Integer> list = new HashSet<Integer>();

The reason for this is that to find a value in an (unsorted) list, you need to check every index in the list until you find the one you want or run out of indexes to check. On average you'll check half the list before finding a value if the value is in the list, or the whole list if it's not. For a hash table, you generate an index from the value you want to find, then you check that one index (it's possible you need to check more than one, but it should be uncommon in a well-designed hash table).

Also, if you use a Set, you get a guarantee that each value is unique, so if you try to add a value that already exists, add will return false. You can use that to slightly simplify the code (note: This will not work if you use a List, because add always returns true on a List):

HashSet<Integer> list = new HashSet<Integer>();

int value;
if(!list.add(value))
    error("",null);

Answer 2

Problems involving ranges often lend themselves to the use of a tree. Here's a way to do that using TreeSet:

public class DisjointChecker {

    private final NavigableSet<Integer> integers = new TreeSet<Integer>();

    public boolean check(int value) {
        return integers.add(value);
    }

    public boolean check(int from, int to) {
        NavigableSet<Integer> range = integers.subSet(from, true, to, true);
        if (range.isEmpty()) {
            addRange(from, to);
            return true;
        }
        else {
            return false;
        }
    }

    private void addRange(int from, int to) {
        for (int i = from; i <= to; ++i) {
            integers.add(i);
        }
    }

}

Here, rather than calling an error handler, the check methods return a boolean indicating whether the arguments were disjoint from all previous arguments. The semantics of the range version are different to in the original code; if the range is not disjoint, none of the elements are added, whereas in the original, any below the first non-disjoint element are added.

A few points may deserve elaboration:

• Set::add returns a boolean indicating whether the addition modified the set; we can use that as the return value from the method.
• NavigableSet is an obscure but standard subinterface of SortedSet which is sadly neglected. Although you could actually use a plain SortedSet here with only minor modifications.
• The NavigableSet::subSet method (like SortedSet::subSet) returns a lightweight view on the underlying set which is restricted to a given range. This provides a very efficient way to query the tree for any overlap with the whole range in one operation.
• The addRange method here is very simple, and runs in O(m log n) when adding m items to a checker which has seen n items previously. It would be possible to make a version which ran in O(m) by writing an implementation of SortedSet which described a range of integers and then using Set::addAll, because TreeSet's implementation of this contains a special case for adding other SortedSets in linear time. The code for that special set implementation is very simple, but involves a lot of boilerplate, so i leave it as an exercise for the reader!