Find the smallest positive integer that does not occur in an array

Question

I am trying out the following codility.com exercise to improve my skills online, I was presented with the following problem.

This is a demo task.

Write a function:

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

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.
Given A = [1, 2, 3], the function should return 4.
Given A = [-1, -3], the function should return 1.

Write an efficient algorithm for the following assumptions:
• N is an integer within the range [1..100,000);
• each element of array A is an integer within the range (-1,000,000..1,000,000).

Copyright 2009– by Codility Limited

rendered description

I solved it using the following solution:

<?php

class Solution {
    public function($A) {
        $posInts = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        $diffs = array_diff($postInts, $A);
        $smallestPosInt = min($diffs);
        return $smallestPosInt;
    }
}

However upon submitting I got the following score:

Now I am very unsure of what I did wrong here or how I can rewrite the code with a better algorithm.

Answer 1

Check out this answer using Javascript in a way that works with the best possible performance -If I am not mistaken- O(N).

function solution(A) {
  const set = new Set(A)
  let i = 1

  while (set.has(i)) {
    i++
  }
  return i
}

Answer 2

I would just loop over (increment) any possible integers:

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    for (; $result <= $maxNumber; $result++) {
        if (!in_array($result, $A)) {
            break;
        }
    }
    return $result;
}

var_dump(solution([1, 3, 6, 4, 1, 2])); // int(5)
var_dump(solution([1, 2, 3])); // int(4)
var_dump(solution([-1, -3])); // int(1)

// As a bonus, this also works for larger numbers:
var_dump(solution([1, 3, 6, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 5, 15])); // int(14)

Edit regarding performance:

As pointed out in the comments (and you already said yourself), this is not a very efficient solution.

While I do not have enough time on my hands currently to do real performance testing, I think this should be close to an O(n) solution: (keeping in mind that I am not sure how arrays are implemented on the C-side of PHP)

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    $values = array_flip($A);
    for (; $result <= $maxNumber; $result++) {
        if (!isset($values[$result])) {
            break;
        }
    }
    return $result;
}
// Not posting the output again because it is naturally the same ;) 

The "trick" here is to flip the array first so that the values become the indexes. Since a) we do not care about the original indexes and b) we do not care if duplicated values overwrite each other, we can safely do that.

Using isset() instead of in_array() should be a lot quicker since it basically just checks if a variable (in this case stored at a specific index of the array) exists and PHP does therefore not have to iterate through the array in order to check whether or not each number we loop over exists within it.

P.S.: After thinking twice I think this may still be closer to O(n*2) because max() probably loops to find the highest value. You could also remove that line and just check against the highest number there is in PHP as an emergency exit, like so: for (; $result <= PHP_INT_MAX; $result++) { ... } as a further optimization. Or maybe just hard-code the highest allowed number as specified in the task.

Answer 3

If we're allowed to modify the input, perform this in place, otherwise create a new array of size n + 1:

For each element encountered in the original array, if it is greater than n + 1 or smaller than 1, assign 0 at the element's index (index - 1 if performing in place); otherwise assign 1 at the index of the array the value is and assign 0 at its own index if it is different. After that run a second traversal and report the first index (index + 1 if performing in place) greater than zero with value 0, or n + 1.

[1, 3, 6, 4, 1, 2]

=>

[1, 1, 1, 1, 0, 1]

report 5