java - Codility MissingInteger task, one case timeout -

the task found first positive integer not present in given array.

i found correct solution, don't understand why solution has time "large" input , bad "medium".

here solution:

import java.util.arrays; import java.util.stream.*;  class solution  {     public int solution(int[] a)      {                 int[] = intstream.of(a).distinct().filter( s -> s > 0 ).toarray();         arrays.sort(a);         int next = 1;          (int = 0; < a.length; i++ )         {             if( a[i] == next )                 next++;             else if ( a[i] > next)                 break;         }          return next;     } } 

and link result: https://codility.com/demo/results/demo8f8ddw-9bk/

the problem specification says expected worst-case time complexity o(n), can't sort data. sorting o(n log n). if sorting solution got accepted anyway, apparently test isn't strict enough, or biggest test case isn't constructed properly.

fortunately, don't have sort data. know front solution @ length of input array, numbers between 1 , input.length interesting. have enough memory keep boolean of them (you store many integers anyway)

public int solution (int[] input) {                                              boolean[] ispresent = new boolean[input.length + 1];                         (int : input) {                                                            if (0 < && < ispresent.length) {                                                      ispresent[i] = true;                                                     }                                                                        }                                                                            (int = 1; < ispresent.length; i++) {                                     if (!ispresent[i]) return i;                                             }                                                                            return input.length + 1;                                                 }