Given an array of integers, return the smallest positive integer not in it

Question

Write a function:

function solution(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.

Assume that:

• 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]

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 in \$O(n^2)\$:

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

Answer 1

That's a nice simple solution, with two problems:

1. It will give incorrect result when A contains all the values in the ranges [1..1000000] or [1..999999], returning undefined instead of 1000001 and 1000000, respectively.
2. It doesn't meet the time complexity requirement, being \$O(n^2)\$ instead of \$O(n)\$.

The first problem is easy to fix by adjusting the end condition of the loop.

The second problem is trickier, and the interesting part of the exercise. Consider this algorithm, that's \$O(n)\$ in time and \$O(1)\$ in space:

• Loop over the elements of A from the start, and for each value A[i], if A[i] - 1 is a valid index in the array, then repeatedly swap A[i] and A[A[i] - 1] until A[i] is in its correct place (value equal to i + 1), or A[i] and A[A[i] - 1] are equal.
  • This should order the values to their right places such that A[i] == i + 1, when possible
• Loop over the elements again to find an index where A[i] != i + 1, if exists then the missing value is i + 1
• If the end of the loop is reached without returning a value, then the missing value is A.length + 1.

Here's one way to implement this in JavaScript:

var firstMissingPositive = function(nums) {
    var swap = function(i, j) {
        var tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };

    for (let i = 0; i < nums.length; i++) {
        while (0 < nums[i] && nums[i] - 1 < nums.length
                && nums[i] != i + 1
                && nums[i] != nums[nums[i] - 1]) {
            swap(i, nums[i] - 1);
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;
};

Note: to verify this, or alternative implementations work, you could submit on leetcode.

Answer 2

How about this solution, which – if I'm not mistaken – should fulfill all requirements:

• create a second array
• run through all elements of the input array
• for each number set the respective key in the second array to true
• run through the second array and return the first key which value comes back as undefined
• if no match is found, return 1, so it will work for an empty input array as well

---

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

---

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{JollyJoker suggested a similar version in the comments using JavaScript's built-ins filter, reduce and findIndex. I fixed the suggested solution for edge cases and added it to the performance test. You can now test all three solutions. Keep in mind that these built-ins come with some overhead.}

^{Janos added code for his algorithm as well now. To complete the performance test, I've added it as well and here's the final fiddle containing all four solutions.}

Answer 3

In order to satisfy the O(N) time-complexity, construct a Set() in O(N) time and space complexity, then use a while loop which is considered constant time relative to N O(N) as well (thank you, wchargin), since the maximum possible number of iterations is equal to N and average performance of a Set#has() operation is O(1). Because O(N + N) = O(N), regarding time complexity, this solution is overall O(N) performance in both time and space:

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

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

  return i;
}

---

^{While this is a relatively simplistic and deceivingly elegant implementation, insertusernamehere's solution is admittedly an order of magnitude faster, when using an array as a perfect hash table for non-negative integers instead.}

Answer 4

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

Be consistent with your spacing. You use a space after for but not for if. The space helps separate language constructs from function calls.

For languages that use braces, always brace your one-liners (explicitly establishes the loop boundary) and prefer to have them on a separate line for readability, maintenance, and debugging (breakpoints!).

What happens if len(A) >= 1,000,000? Use the length of the array instead of an arbitrary value. See below.

---

You can simplify this problem by filtering/partitioning any non-positive value from the array. Once you have a filtered array of positive integers, you can use the filtered length to determine the upper-bound of the lowest positive integer. For a distinct sequence of integers \$D = [1, 2, 3, ..., n]\$, the lowest positive integer is guaranteed to be \$n+1\$. If you remove any value from \$D\$ and replace it with any other value (or simply remove it), then the lowest positive integer of \$D\$ is in the range \$[1, n]\$. To find it, we can simply track integers in a boolean table, upto \$n\$, marking the ones witnessed. A linear search of the boolean array for the first unmarked entry will give us a zero-based index of the lowest positive integer missing. Add one to make it one-based once again. Filtering, marking witnesses, and searching are all linear operations.

Note - Since you know the upper-bound, you can narrow your range further by making a second filter pass which removes any elements larger than the array length. Would help with data locality if you have smallish arrays loaded with largish values.

While using a boolean array does meet your space complexity requirement, a constant space solution does exist. Remember that every element in your filtered array is positive, so we can repurpose the sign bit of each value as a signal that we've witnessed a value of the sequence. We can use the indices of the filtered array the same way we did the boolean array above. Rather than search for the first element marked false (unwitnessed), we search for the first value that is still positive.

solution(A)
    Filter non-positive values from A
    Filter values larger than min(N-1, 999999) from A
    For each int in A that wasn't filtered out
        Let a zero-based index be the absolute value of the int - 1
    For each index upto min(N-1, 999999)
        if A[index] is positive, return the index + 1 (to one-based)
    otherwise return min(N, 100000)

So an array \$A = [ 1, 2, 3, 5, 6]\$, would have the following transformations:

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]

A linear search for the first positive value returns an index of 3. Converting back to a one-based index results in \$solution(A) = 3 + 1 = 4\$

Answer 5

One thing to note is how much space you are allowed to use. You can use up to O(n) space, (enough to make a full copy of your data). Your code currently is slow because it uses O(n) in statements, each of which are O(n). This means that if only there existed a data structure on which in statements were O(1), you would have solved your problem. Thankfully Set has exactly this property. Therefore, the only change you need to make to your solution is turn your list into a set.

Answer 6

You can trivially find a faster solution than the one you've already given, by simply sorting the array first, stripping all non-positive integers and start the search from there -- this makes the algorithm an \$O(n \log n)\$ algorithm in the worst case and in the best case an \$O(n)\$ algorithm and doesn't require any extra space.

Alternatively, just add all the positive numbers to a set and find the smallest positive number that's not in that set. If you want to do this in less than \$O(n \log n)\$ time, you need to use a bitvector; go through all the elements and set bit n in the vector to true, when the element you're inspecting is equal to n. This will take \$O(n)\$ time and \$O(n)\$ space.

To get the size of the bit vector simply find the largest integer (and the smallest while you're at it) and allocate that many bits. This can also be done in \$O(n)\$ time. If the smallest integer isn't 1, then the number you're looking for is 1.

Answer 7

In JavaScript you can do this:

1. First, remove duplicates if any

    var A=[4,3,2,1,0,1,-3];
    const remove_duplicates = A.filter((number, index) => {
          return A.indexOf(number) === index
    })

2. Secondly, order your array using the JavaScript Array.sort() method, with complexity \$O(n\log(n))\$ (explained here):

    const sorted = remove_duplicates.sort(function(a, b){return a-b});
    //returns the array ordered [-3,0,1,2,3,4]
   

3. Only iterate over the ordered array. For every value, check if the value is bigger than 0 and if the next element on the array is not equal to the current value + 1.

    // find smallest positive integer not in sorted greater than 0
    // return only valid number, unless all negative values else return 1
    const result = sorted.map((number, index) => {
        if (number > 0 && sorted[index + 1] !== sorted[index] + 1) {
            return sorted[index] + 1
        }
    }).filter(number => number !== undefined)[0]

    return result === undefined ? 1 : result

Answer 8

Using a set makes the problem O(N lg N) as associated directories are lg N for each insert, delete and find. Unless you use the hash version of the associated directories, in which case you can't find next in O(1) as worst case is O(N).

Sorting with a comparison function always result in O(N lg N), but other specialized sorts doesn't, like counting sort.

So we could try with a specialization of counting sort, lets call it existence sort as we are not interested in how many but only in if it exists.

Further we prune the range of numbers in the original array to only those between 1 and 100000 included.

Pseudo code for a this method:

min = 1
max = 100000

bool num[100000] = false // 100000 long array of bool, add 1 (one) if your language array index start at 0 (zero)


for (i = 1; i < 1000000; i++) {
  can = A[i];
  if(can >= min && can <= max) {
    num[can] = true;    // register numbers that exist in our range
  }
}

for (i = min; i <= max; i++)
  if (!num[i])
    return i;

Answer 9

Here is a PHP solution (initial test):

<?php
$a = array(
    2, 1, 3, 5, 6, 7,
);

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    $i = 0;

    while(in_array(++$i, $a)){}

    return $i;
}

echo solution($a);

and here is a refactored version based on feedback in the comments below:

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    /**
     * Lowest possible number in set
     * -1 so it starts counting at
     * -1000000
     */
    $i =-1000001;
    $c = 1;

    while($c){
        $i++;
        if(($i > 0 && !in_array($i, $a)) || $i > 1000000){
            $c = 0;
        }
    }

    /**
     * If $i is negative, the lowest positive
     * integer in set will be 1, otherwise it
     * will be the set value of $i unless $i
     * is out of range for this task
     */
    if($i <= 1000000){
        return ($i < 1) ? 1 : $i;
    }
    return 'Value out of range';
}

Answer 10

The following solution in Java should be within the boundaries of time and space complexity:

public int solution(int[] A)
{
    java.util.HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(A.length); //O(n) space
    for (int i : A) // O(N)
    {
        if (!map.containsKey(i))
        {
            map.put(i, i);
        }
    }
    int smallestPositive = 1;
    for (int i = 1; i < 1000001; i++) // ~O(N)
    {
        if (map.containsKey(i) && map.get(i) <= smallestPositive)
        {
            smallestPositive = map.get(i) + 1;
        }
    }
    return smallestPositive;
}

I was about to write that you might even ditch the HashMap and loop over A in the second loop as 1,000,000 is a constant and should be negligible, but it looks like they specifically made a point in the question that \$N\$ is 100,000 which is smaller so you can consider the second loop to be of \$O(n)\$ time.

It sums up to \$O(n) + O(n) = O(n)\$ time and \$O(n)\$ space for the map.