Find the smallest positive integer that is absent from a given array 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 &lt; 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&lt;A.Length; i++)
    {
        myArr.Add(A[i]);
    }
    for ( int i = 1; i &lt; 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?
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 &lt; a.Length; index++) {
    if (a[index] &lt; 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] &gt; 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.