NotInArray.java

import java.util.HashSet;

class NotInArray {
  public static void main(String[] args) {
    int[] input = new int[] { Integer.MAX_VALUE, 3, 4, 7, 9, Integer.MIN_VALUE };
    System.out.println(notInArray(input));
  }

  private static int notInArray(int[] input) {
    HashSet<Integer> possibleValues = new HashSet<>();

    for(int i = 0; i<input.length; i++) {
      int current = input[i];
      if(current > Integer.MIN_VALUE && !possibleValues.contains(current-1))
        possibleValues.add(current-1);
      if(current < Integer.MAX_VALUE && !possibleValues.contains(current+1))
        possibleValues.add(current+1);
      if(possibleValues.contains(current)) possibleValues.remove(current);
    }
    if(possibleValues.size() > 0) return possibleValues.iterator().next();
    else throw new RuntimeException("Oh oh!");
  }
}