Return to Revisions

Stupid edge-cases!

While doing some testing for coming up with a better version for the First missing positive question, I added a bunch of more test cases and compared several different methods with each other. Then I found the following problems:

Input [-5] returned 2147483647 but expected 1
Input [-5, -4, -3] returned 2147483647 but expected 1
Input [0, 0, 0, 0] returned 2147483647 but expected 1
Input [] returned 2147483647 but expected 1

To correct these problems, I added some edge-case checking; to check for array where there are no positive integers. As these really are edge-cases, I haven't decided how to handle these. As there technically isn't a clear "first missing positive number". If I would have handled 7 8 9 as return 1 then I would have returned 1 for these edge cases also, but I feel that wouldn't be expected behavior from this algorithm so therefore I decided to throw an exception.

The new code is:

public int simonNew(int[] array) {
 boolean[] foundIntegers = new boolean[array.length];
 int smallestPositive = Integer.MAX_VALUE;
 for (int i : array) {
 if (i > 0 && i < smallestPositive)
 smallestPositive = i;
 }
 if (smallestPositive == Integer.MAX_VALUE)
 throw new IllegalArgumentException("Array must not be null and must contain at least one positive integer");
 for (int i : array) {
 if (i < smallestPositive)
 continue;
 int index = i - smallestPositive;
 if (index < foundIntegers.length)
 foundIntegers[index] = true;
 }
 for (int i = 0; i < foundIntegers.length; i++) {
 if (!foundIntegers[i])
 return i + smallestPositive;
 }
 return foundIntegers.length + smallestPositive;
}