Find the smallest positive integer that is absent from a given array

Question

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find out how to make algorithms more efficient.

I've been practising with the the demo challenge in Codility:

Write a function that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5. The given array can have integers between -1 million and 1 million.

I started with a brute-force algorithm:

public int solution(int[] A)
{
    for ( int number = 1; number < 1000000; number ++)
    {
        if (doesContain(A, number)){}
        else return i;
    }
    return 0;
}

This passed all tests for correctness but scored low on performance because the running time was way past the limit, time complexity being \$O(N^2)\$.

I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere).

public int solution(int[] A)
{
    ArrayList myArr = new ArrayList();
    for (int i=0; i<A.Length; i++)
    {
        myArr.Add(A[i]);
    }
    for ( int i = 1; i < 1000000; i++)
    {
        if (myArr.Contains(i)){}
        else return i;
    }
    return 0;
}

Alas, the time complexity is still at \$O(N^2)\$ and I can't find explanations of how to cut down time.

I know I shouldn't be using brute force, but can't seem to think of any other ways... Anyone have an explanation of how to make this algorithm more efficient?

Answer 1

I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere).

As was mentioned in the comments, for your purpose, there is no significant difference in performance between int[] and ArrayList. Both store their data in a similar way, and both will have to iterate through the array to check for Contains. So that doesn't help anything.

---

Sorting

You mention sorting in the title of your question. But you don't actually do any sorting. Let's look at the challenge:

Write a function that, given an array A of N integers, returns the smallest >positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5. The given array can have integers between -1 million and 1 million.

We need to know whether 1, 2, 3, etc are in the input. You can do this, by checking each and every option, one at a time. Since you don't know whether 1 would be at the start, or at the end of the array, you have to check the entire thing each and every time. That's inefficient.

However, if you sort the input, the array becomes somewhat predictable. You can loop through the sorted array until you find the first positive number. Is it higher than 1? Then we can return 1, since that is the smallest possible integer that's not in the list - the smallest positive integer is >1 after all. If it equals 1, we can go to the next element and check its value. If it is another 1, move on. If it is >2, we can return 2, else we must move on. And repeat.

In that way, what we have done, is sorting the array (\$O(n logn)\$), and then looping through it once. All in all, that's still \$O(n logn)\$.

public int solution(int[] a) {
  // sort
  Array.Sort(a);
  var answerCandidate = 1;

  // Find the first nonzero positive number.
  for(var index = 0; index < a.Length; index++) {
    if (a[index] < answerCandidate) {
      continue;
    } else if(a[index] == answerCandidate) {
      // Oops, we found our candidate in the list, so we move to the next one.
      // Since the list is sorted, we know the next one can only be farther
      // on in the list, so we don't need to restart the loop.
      answerCandidate++;
    } else {
      // In this case a[index] > answerCandidate. This means that we haven't found
      // the candidate in the list, so we can return answerCandidate. Break so
      // that we can handle the case where we pass the end of the array at the same time.
      break;
    }
  }

  return answerCandidate;
}

We can still make a marginal improvement by searching for the first positive number using a binary search on our sorted list.

Answer 2

The algorithm provided by the OP presumes that the array is important and preserves the original array. In addition, the displayed algorithm seeks an "instantaneous answer", as if the routine may be interrogated at any point to get that answer at the point in time.

All that is important here is the output - a single number. Any other information used to get that output can be discarded. As such, any information that is not useful for the solution (such as negative elements of the array) can be discarded with extreme prejudice. And once an element has been used to work towards a solution, it too can be discarded or forgotten.

Thus, the algorithm should not be trying to find the contiguous elements, but rather the hole that is there (as is stated in the original question).

I am not a java programmer, so I will answer with pseudo-code. The following alternative approach focuses on the speed, and in doing so is willing to sacrifice space. Because the input array is random, some semblance of state (i.e. the contiguous blocks) is required.

input: array [A]

Create capture array of size 1 million Boolean[B]
traverse [A] (read values)
    discard values <= 0
    set [B](value) = true
traverse [B]
    Stop at first false. 

Solution: index[B] at the stopping point

This is a potential max of \$O(2n)\$ if a random access array is used.

Answer 3

Better complexity can be achieved using a heap. The input array can be organized into a min-heap in \$O(n)\$ time with negative integers dropped. Then the smallest number can be popped one by one until the target number is found. The complexity of this algorithm is \$O(n + k\log{n})\$ where \$k\$ is the insertion index of the target number among the sorted sequence of positive numbers.