Discussion on: Java Daily Coding Problem #001

[Joan Verdaguer]

If you're crazy about complexity's O, I have the impression it would be better to start by sorting it and then going through the array starting both from the beggining and the end, but only once, so it becomes O(nlogn). It's probably less readable though.

Arrays.sort(arr);
int i = 0;
int j = arr.length - 1;
while(i < arr.length && j >= 0)
{
  int sum = arr[i] + arr[j];
  if(sum == k)
    return true;
  else if (sum > k)
    j--;
  else
    i++;
}
return false;

Andrei's solution was very smart as well, and I guess depending on complexity of contains and add of the Set object, you could get an algorithm with the same complexity.