I went through a few posts about the O(n) solution. But never mentioned about the integer overflow problem. Taking hash map solution for example,

when checking left or right boundary, the solution only simply use map.containsKey(key -1) or map.containsKey(key+1) to do it. But do you think about what if the key is a Integer_MIN_VALUE or Integer_MAX_VALUE? Giving you an example, given array {2147483647, -2147483648, -2147483647}, then most of your functions would lead to an integer overflow.