Efficient search for not empty intersection (Java)
disjoint-union, java, processing-efficiency
Solution
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);
Problem
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); } ```