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

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

Solutons:


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.

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.

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.

Related Solutions

How to download package not install it with apt-get command?

Use --download-only: sudo apt-get install --download-only pppoe This will download pppoe and any dependencies you need, and place them in /var/cache/apt/archives. That way a subsequent apt-get install pppoe will be able to complete without any extra downloads....

What defines the maximum size for a command single argument?

Answers Definitely not a bug. The parameter which defines the maximum size for one argument is MAX_ARG_STRLEN. There is no documentation for this parameter other than the comments in binfmts.h: /* * These are the maximum length and maximum number of strings...

Bulk rename, change prefix

I'd say the simplest it to just use the rename command which is common on many Linux distributions. There are two common versions of this command so check its man page to find which one you have: ## rename from Perl (common in Debian systems -- Ubuntu, Mint,...

Output from ls has newlines but displays on a single line. Why?

When you pipe the output, ls acts differently. This fact is hidden away in the info documentation: If standard output is a terminal, the output is in columns (sorted vertically) and control characters are output as question marks; otherwise, the output is...

mv: Move file only if destination does not exist

mv -vn file1 file2. This command will do what you want. You can skip -v if you want. -v makes it verbose - mv will tell you that it moved file if it moves it(useful, since there is possibility that file will not be moved) -n moves only if file2 does not exist....

Is it possible to store and query JSON in SQLite?

SQLite 3.9 introduced a new extension (JSON1) that allows you to easily work with JSON data . Also, it introduced support for indexes on expressions, which (in my understanding) should allow you to define indexes on your JSON data as well. PostgreSQL has some...

Combining tail && journalctl

You could use: journalctl -u service-name -f -f, --follow Show only the most recent journal entries, and continuously print new entries as they are appended to the journal. Here I've added "service-name" to distinguish this answer from others; you substitute...

how can shellshock be exploited over SSH?

One example where this can be exploited is on servers with an authorized_keys forced command. When adding an entry to ~/.ssh/authorized_keys, you can prefix the line with command="foo" to force foo to be run any time that ssh public key is used. With this...

Why doesn’t the tilde (~) expand inside double quotes?

The reason, because inside double quotes, tilde ~ has no special meaning, it's treated as literal. POSIX defines Double-Quotes as: Enclosing characters in double-quotes ( "" ) shall preserve the literal value of all characters within the double-quotes, with the...

What is GNU Info for?

GNU Info was designed to offer documentation that was comprehensive, hyperlinked, and possible to output to multiple formats. Man pages were available, and they were great at providing printed output. However, they were designed such that each man page had a...

Set systemd service to execute after fstab mount

a CIFS network location is mounted via /etc/fstab to /mnt/ on boot-up. No, it is not. Get this right, and the rest falls into place naturally. The mount is handled by a (generated) systemd mount unit that will be named something like mnt-wibble.mount. You can...

Merge two video clips into one, placing them next to each other

To be honest, using the accepted answer resulted in a lot of dropped frames for me. However, using the hstack filter_complex produced perfectly fluid output: ffmpeg -i left.mp4 -i right.mp4 -filter_complex hstack output.mp4 ffmpeg -i input1.mp4 -i input2.mp4...

How portable are /dev/stdin, /dev/stdout and /dev/stderr?

It's been available on Linux back into its prehistory. It is not POSIX, although many actual shells (including AT&T ksh and bash) will simulate it if it's not present in the OS; note that this simulation only works at the shell level (i.e. redirection or...

How can I increase the number of inodes in an ext4 filesystem?

It seems that you have a lot more files than normal expectation. I don't know whether there is a solution to change the inode table size dynamically. I'm afraid that you need to back-up your data, and create new filesystem, and restore your data. To create new...

Why doesn’t cp have a progress bar like wget?

The tradition in unix tools is to display messages only if something goes wrong. I think this is both for design and practical reasons. The design is intended to make it obvious when something goes wrong: you get an error message, and it's not drowned in...

OpenSSH: How to end a match block

To end up a match block with openssh 6.5p1 or above, use the line: Match all Here is a piece of code, taken from my /etc/ssh/sshd_config file: # Change to no to disable tunnelled clear text passwords PasswordAuthentication no Match host 192.168.1.12...

Redirecting the content of a file to the command “echo”

You can redirect all you want to echo but it won't do anything with it. echo doesn't read its standard input. All it does is write to standard output its arguments separated by a space character and terminated by a newline character (and with some echo...