Simon Krenger

So recently I stumbled across a programming quiz to which I later returned because it somehow fascinated me.

Problem

Finding the first available number (or the smallest missing number) in a list is a common problem in Computer Science (for example for Defragmenting or generating keys) and describes the search for the smallest natural number, which is not part of a set X of natural numbers. X is a set of distinct natural numbers (and being a set, is not ordered).

We are now looking for a function with linear worst-case time complexity O(n).

Example

We define X as a set of distinct natural numbers:

X = {23,9,12,0,11,1,13,7,21,14,5,4,17,19,3,6,2}

So in this set, we find that the number 8 is the first available number (smallest missing number). So running the algorithm over the above set should return 8.

Solution

Finding a solution is not trivial due to the time complexity requirement. The easiest way to solve this problem would be to sort the list and then go through the list and look for the smallest missing number. The problem with this approach is that sorting the list takes O(n log n) in the worst case. So we’ll have to look for another solution.

One possible solution to this problem is described here on StackOverflow by Ants Aasma. This solution has a worst-case time complexity of O(3n), simplified O(n).

Here is the Java code for the above algorithm:

private static int first_available_number(int[] numbers) {
	
	for(int i=0; i < numbers.length; i++) {
		int target = numbers[i];
		while(target < numbers.length && target != numbers[target]) {
			int new_target = numbers[target];
			numbers[target] = target;
			target = new_target;
		}
	}
	
	for(int i=0; i < numbers.length; i++) {
		if(numbers[i] != i) {
			return i;
		}
	}
	return numbers.length;
}