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;
  }
}
  • 11
    I do not know the guidelines of this site, but to me this is not a code review question, as you seem to expect to be given an algorithm that you have not found yourself. – Carsten S Oct 29 '17 at 15:29
  • 3
    @CarstenS It is a valid code review post, working code, clear explanation, asking for advice. – CodeYogi Nov 3 '17 at 6:18
  • Easy Way ----------------- function solution(Arr) { // write your code in JavaScript (Node.js 8.9.4) const min = Math.min(...Arr); const max = Math.max(...Arr); if (min < 0 && !Arr.includes(1)) { return 1; } let smallestPIntNot = []; for (let i=1; i<=max+1; i++) { if (!Arr.includes(i)) { smallestPIntNot.push(i); } } return smallestPIntNot[0]; } – Monty Nov 29 at 12:50

10 Answers 10

up vote 24 down vote accepted

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.

  • What is the time complexity of this? It isn't even that easy to confirm that it terminates, not to mention is O(n) – Oscar Smith Oct 28 '17 at 20:49
  • 3
    The exchange loop runs in O (n): That's because every exchange operation puts one value x into its right place that wasn't in the right place before, and because at most N values can be in the wrong place there can be at most N exchange operations. – gnasher729 Oct 28 '17 at 22:18
  • @gnasher729 why do you only count the number exchanges, but not the exchanges themselves towards complexity? I believe, the algorithm above is a kind of comparison-based sorting, in a way similar to insertion sort... so, we aren't even talking about O(log n) here... – wvxvw Oct 29 '17 at 10:27
  • 1
    swapping makes this algorithm complex. You can write the number in the correct position of a fresh array (or discard them when they are to large) a second iteration over that array finds the correct number. – Jens Schauder Oct 29 '17 at 13:28
  • @JensSchauder You could, but you would have O(n) additional space complexity, while this algorithm only uses O(1); just to get rid of some perceived complicatedness. – Sanchises Oct 29 '17 at 16:30

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.

  • 1
    @PatrickRoberts, using set makes it O(N lg N). – Surt Oct 29 '17 at 7:34
  • 1
    @PatrickRoberts Can you elaborate why you say: "You shouldn't use an array as an associative array."? I'd say that the function uses a "sparse" array. This "holey" array acts like a normal array and the length is calculated correctly, even if you would set the key like result['10']. Whereas when using an "associative" value, like result['ten'] the value is not calculated correctly. Here's a this fiddle for testing. – insertusernamehere Oct 29 '17 at 7:48
  • 1
    I could be wrong, but I don't think a sparse array has a lookup time of O(1), making this probably O(n log n). – Sanchises Oct 29 '17 at 16:13
  • 1
    es6:a => a.filter(x => x > 0 && x < a.length).reduce((acc, curr) => { acc[curr] = true; return acc; }, []).findIndex(y => !y); – JollyJoker Oct 30 '17 at 8:52
  • 1
    @tokland I don't know whether it's idiomatic to be honest. I just like it but I'm good with both ways of writing conditions. At least there is a rule on ESLint for it - but it goes either way to require or to disallow it. Wordpress' JavaScript coding standards suggests using Yoda conditions – but then again they do it, because it's in their PHP coding standards as well. And yes, of cource you're right that !result[i] would be equally good here. – insertusernamehere Oct 30 '17 at 14:17

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.

  • Thanks, this is also O(N) or O(N * log(N)), I will run a timed test between your answer and insertusernamehere. Fastest gets it. – Philip Kirkbride Oct 29 '17 at 1:31
  • a "in" test on a set is not O(1) – Jens Schauder Oct 29 '17 at 13:29
  • 1
    @JensSchauder Even if it was O(log N) (which it isn't), it doesn't matter. O(N + log N) = O(N). – Patrick Roberts Oct 29 '17 at 14:42
  • 4
    @JensSchauder: Yes, it is: a Set in V8 or any other reasonable engine is implemented as a hash table with O(1) lookup. Patrick: it would matter; if set.has(i) took O(log N) time, then you would have Ω(N log N) time worst-case, because you invoke has as many as N times. – wchargin Oct 29 '17 at 15:16
  • @wchargin as I stated in my answer, the while loop is in constant time relative to N because the length of the array and the range of numbers to check are not related. – Patrick Roberts Oct 29 '17 at 15:17
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
    For each int in filtered
        Let a zero-based index be the absolute value of the int - 1
        If the filtered range can be accessed by that index
            Make the value in filtered[index] negative
    For each index in filtered
        if filtered[index] is positive, return the index + 1 (to one-based)
    otherwise return the length of filtered + 1 (to one-based)

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]
abs(A[4]) = 6, to_0idx = 5, A[5] is inaccessible,          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\$

  • In the case that the integers in the array are not distinct I think the statement "Filter non-positive values from A" needs to be complemented with "Filter non-positive & duplicate values from A". I am not sure if .distinct() is linear complexity though. – XDS Nov 11 at 17:32
  • Addendum: If the integers are not distinct then maybe (and I could be wrong here) a better way to tackle the resulting issue would be to modify "Make the value in filtered[index] negative" to read "If filtered[index] is not already negative then make the value in filtered[index] negative". Again I am not entirely sure about this. – XDS Nov 11 at 17:52
  • I'm getting TIMEOUT ERROR for large_1(1.66 sec), large_2( >6.00 sec, 4.97 sec) and large_3(1.080 s) performance tests. On my macbook pro I'm getting 10ms for 1000000 random positive array – Alexey Sh. 2 days ago

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.

  • Thanks, can you expand on this. Would the array A be consider a set here? – Philip Kirkbride Oct 29 '17 at 1:20
  • My answer is basically the same as Patricks. The key is to make a Set so you get fast membership testing. – Oscar Smith Oct 29 '17 at 5:34

In JavaScript you can do this:

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

    var A=[4,3,2,1,0,-3];
    A.sort(function(a, b){return a-b});
    //returns the array ordered [-3,0,1,2,3,4]
    
  2. 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.

    function(A){
        for(var i=0;i<A.length-1;i++){// iterate until  penultimate element
            if(A[i]>0 && A[i+1]!=(A[i]+1)){
                return (A[i]+1);
            }
        }
    }
    
  • 3
    Except that O(n log n) > O(n), which is the required time complexity. This does not satisfy the requirements for the requested code. – Patrick Roberts Oct 29 '17 at 0:30

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.

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;
  • Sorting with a comparison based method is only $O(n \log n)$ in the worst case. It's trivial to make it $O(n)$ in the best case (even for multiple such cases at the same time), and gradually move from $O(n)$ to $O(n \log n)$ as the list is "less" sorted. – Clearer Oct 29 '17 at 21:58

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';
}
  • 1
    I'd say that this is the same as the OP's code: This means it is O(n^2) instead of O(n) and does not fulfill the requirement of the question. – lampshade Nov 2 '17 at 11:00
  • @lampshade I have made amendments to the function above - now checks for a range of -1000000 to +1000000 inclusive. – Shaun Bebbers Nov 2 '17 at 13:31
  • 1
    You don't need to test all negative values actually. What I meant is: You have a while loop which runs in O(n) which uses in_array which is also O(n) so your time complexity is O(n^2). Hope this makes sense. – lampshade Nov 2 '17 at 13:41

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.

protected by Jamal Feb 1 at 5:54

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.