Codility solutions - lesson2, exercise: MissingInteger

Content of Codility exercise:

Write a function:

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

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.

For example, given:

  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].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public int solution(int[] A) { //tmp array to store each number from A on position equal its number minus 1 int tmpB[] = new int[A.length]; int maxElement = 0; for (int i=0; i<A.length; i++){ //only element lager than zero and smaller than A size can be considered if (A[i] <= A.length && A[i]>0){ tmpB[A[i]-1] = A[i]; } } //if tmpB array contains zero element the solution will be index of mentioned element increased by 1 //if tmpB array doesn't contain zero element solution will be th biggest element increased by 1 for(int i = 0; i<tmpB.length; i++){ if (tmpB[i] == 0){ return i+1; } if (maxElement < tmpB[i]){ maxElement = tmpB[i]; } } return maxElement+1; }