Find the missing integer in Codility

Question

I need to "Find the minimal positive integer not occurring in a given sequence. "
  A[0] = 1    
  A[1] = 3    
  A[2] = 6
  A[3] = 4    
  A[4] = 1    
  A[5] = 2, the function should return 5.

Assume that:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

I wrote the code in codility, but for many cases it did not worked and the performance test gives 0 %. Please help me out, where I am wrong.

    class Solution {
    public int solution(int[] A) {

    if(A.Length ==0) return -1;
    int value = A[0];
    int min = A.Min();
    int max = A.Max();
    for (int j = min+1; j < max; j++)
    {
      if (!A.Contains(j))
      {
          value = j;
          if(value > 0)
          {
             break;
          }
      }
    }

    if(value > 0)
    {
      return value;
    }
    else return 1;
  }
}

The codility gives error with all except the example, positive and negative only values.

Answer 1

Edit: Added detail to answer your actual question more directly.

"Please help me out, where I am wrong."

In terms of correctness: Consider A = {7,2,5,6,3}. The correct output, given the contents of A, is 1, but our algorithm would fail to detect this since A.Min() would return 2 and we would start looping from 3 onward. In this case, we would return 4 instead; since it's the next missing value.

Same goes for something like A = {14,15,13}. The minimal missing positive integer here is again 1 and, since all the values from 13-15 are present, the value variable will retain its initial value of value=A[0] which would be 14.

In terms of performance: Consider what A.Min(), A.Max() and A.Contains() are doing behind the scenes; each one of these is looping through A in its entirety and in the case of Contains, we are calling it repeatedly for every value between the Min() and the lowest positive integer we can find. This will take us far beyond the specified O(N) performance that Codility is looking for.

By contrast, here's the simplest version I can think of that should score 100% on Codility. Notice that we only loop through A once and that we take advantage of a Dictionary which lets us use ContainsKey; a much faster method that does not require looping through the whole collection to find a value.

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int[] A) {

        // the minimum possible answer is 1
        int result = 1; 
        // let's keep track of what we find
        Dictionary<int,bool> found = new Dictionary<int,bool>();

        // loop through the given array  
        for(int i=0;i<A.Length;i++) {
            // if we have a positive integer that we haven't found before
            if(A[i] > 0 && !found.ContainsKey(A[i])) {
                // record the fact that we found it
                found.Add(A[i], true);
            }
        }

        // crawl through what we found starting at 1
        while(found.ContainsKey(result)) {
            // look for the next number
            result++;
        }

        // return the smallest positive number that we couldn't find.
        return result;
    }
}