Many of the answers here outline algorithms or provide code that solves the problem, which is very helpful. Amazingly, many of the top answers are all (essentially) variations on the same algorithmic insight. In fact, by walking through a particular line of reasoning, we can reinvent them in a way that gives more intuition for why they work correctly.
Let's begin with some simple observations. First, if we have an array of n items, then the smallest missing integer must be one of 1, 2, 3, ..., n, or n+1. The reason why is that if any of 1, 2, 3, ..., or n isn't present in the array, then the smallest value in that range that's missing must be the one we want. Otherwise, if all the values 1, 2, 3, ..., and n are in the array, then the smallest missing value is n+1.
This insight is helpful for us because it allows us to reframe what we're looking for. Specifically, our job will be to track which of the numbers 1, 2, 3, ..., and n happen to be in the original array somewhere. If we can do that, it will be relatively straightforward to solve the problem. Once we know which items are present, we can count up 1, 2, 3, ..., n until we find the first number that's missing. If none of those values are missing, then the answer is n+1.
Now, our goal is to figure out how to accomplish this while using a small amount of time and a small amount of space.
Let's begin with an approach that uses more time and space than we're allowed to, then see how to optimize it down to O(n) time and O(1) auxiliary space. We'll maintain an auxiliary set of values so that it's easy for us to see what's present in the array. We'll then iterate over the array and, for each value between 1 and n, inclusive, we'll add it to the set. Then, we'll count upward to see which value is missing. Here's some code for this:
# Initial implementation; doesn't meet the time or
# space bounds.
def first_missing_integer(arr):
# Track which items are used
used = set()
# Add each item from the array if it's in range
for i in arr:
if 1 <= i <= len(arr):
used.add(i)
# Count upward as 1, 2, 3, ..., n to see if any of
# those are the values we want.
for i in range(1, len(arr)):
if i not in used:
return i
# If not, the answer is n+1.
return len(arr)
How fast is this, and how much space does it take? Well, maintaining an auxiliary set requires O(n) auxiliary storage space. We're looping over all n items and adding them to a set, which takes expected time O(n). Then, we count upward from 1 to n, querying our set, which takes expected time O(n). Overall, this means that our algorithm uses expected O(n) time and O(n) auxiliary storage space. We're short of our goal in two ways:
- We'd like something that uses O(1) auxiliary space, not O(n) auxiliary space.
- We'd like something that runs in worst-case O(n) time, not expected O(n) time.
To address these issues, let's whittle down the space usage. Right now, we're using an auxiliary set. However, we know that everything in the set is going to be a value between 1 and n, inclusive. That might then lead us to ask: is there a better data structure we could use to store this set?
Since we know the exact range of values that we're going to be storing, one reasonable option here would be to switch from a hash table to a bit vector. We'll make an array of n bits, all initially 0. Whenever we see a value in the appropriate range, we'll flip the corresponding bit to a 1. This means that we no longer need to use hashing at all, and the space overhead is down to n bits of memory rather than n words of memory. It's still O(n) space, but with a much smaller leading coefficient. Nifty!
Here's what this implementation might look like:
# Improved implementation using a bitvector. This still
# doesn't meet the space bounds, but does meet the time
# requirements.
def first_missing_integer(arr):
# n-element bitvector to track which items are
# present. False means the item is not here, and
# True means the item is here.
used = [False] * len(arr)
# Mark each item from the array if it's in range
for i in arr:
if 1 <= i <= len(arr):
# The values range from 1 to n, but our
# array indices run from 0 to n-1, so we
# need to subtract 1 from the value.
used[i - 1] = True
# Scan the bits to find the first one that wasn't
# set.
for i in range(len(arr)):
if not used[i]:
# As above, our indices are shifted here
# in that index i corresponds to the value
# i + 1.
return i + 1
# If not, the answer is n+1.
return len(arr)
This is an improvement over our previous approach. We now run in worst-case O(n) time because no hashing or randomness are required. And our space usage has dropped: we're now using n auxiliary bits. But that's still O(n) auxiliary memory. That's still not good enough. Can we address this?
The trick here is that we are only allowed to use O(1) auxiliary storage space, not O(1) total space. That is, we are allowed to modify our original array however we'd like, provided that we only use O(1) memory on top of that array. And that opens up an interesting possibility: can we use the array itself as our bitvector? That is, instead of allocating a secondary bitvector to track what's present, could we creatively modify our original array to implicitly represent this bitvector?
Fortunately, the answer is yes. And not only is it "yes," but there are many, many different ways to do this. In fact, most of the top answers on this question are essentially variations on the theme of "encode the bitvector within the array itself."
In order for this idea to work, we need some way of "marking" positions in the array. Specifically, we want to "mark" position x in the array if the number x+1 exists somewhere. What could we use to mark that position? Well, what about using the number itself? We are allowed to rearrange the items in the array however we'd like. Let's use the following system: if the value x is in the array, it should end up in position x-1. Then, we can check if x is present by seeing whether arr[x - 1] == x. This implicitly encodes our bitvector by using the position of each element.
Turns out, there's a nice way to do this. Look at the first element of the array. If that element is 0, negative, or bigger than n+1, we don't need to do anything with it because it's not helpful to us. Otherwise, it's between 1 and n, and it needs to go somewhere in the array. Specifically, if the value we're looking at is x, we want to place x at position x - 1. There are two options for how this can proceed.
- If the item at position x - 1 is already equal to x, then nothing more needs to be done to put x at position x - 1.
- Otherwise, there's some other item at position x - 1. Swap that item with x. That item in turn needs to be placed somewhere, so repeat this process.
If we scan across the array from left to right, displacing and moving items like this as appropriate, then we'll end up moving each item at most once. Why? Because an item is only moved when it's either (1) swapped into the position it should be or (2) isn't in a position where it should be and is swapped out in favor of another element. This means that the swaps collectively take time O(n), with only O(1) auxiliary space needed. (Those of you with a background in modern algebra might recognize this as essentially figuring out the cycle decomposition of a partial permutation of the elements 1, 2, ..., n and inverting it.)
Once we've swapped everything around, we can then use our previous strategy of counting upward from 1, 2, 3, ..., up to n to see which item is missing. Instead of checking a bitvector, we'll check what's present at each position in the original array.
Here's what this looks like:
# Runs in O(n) time and uses O(1) auxiliary space, but
# rearranges the elements of the array
def first_missing_integer(arr):
# Move each item x where 1 <= x <= n to position
# x - 1. We sweep from left to right, moving items
# as needed.
for i in range(len(arr)):
# Which item is here?
toPlace = arr[i]
# This item needs to swap with index toPlace - 1
# unless (1) the item isn't in the range from
# 1 to n, (2) the item at index toPlace - 1 is
# already at the proper index.
while 1 <= toPlace <= len(arr) and arr[toPlace - 1] != toPlace:
arr[i], arr[toPlace - 1] = arr[toPlace - 1], arr[i]
toPlace = arr[i]
# At this point, the array is structured so that if
# x appears in the array for some 1 <= x <= n,
# then arr[x - 1] == x. To find the missing integer,
# we count up from 1, 2, 3, ..., n to see which
# is the first missing value.
for i in range(len(arr)):
if arr[i] != i + 1:
return i + 1
# All values from 1 to n are present, so n+1 is
# the smallest missing one.
return len(arr)
This approach is closely related to the one proposed by Abhijit Sarkar, the one proposed by Anubis, and the one proposed by sarkar, among others. Since it purely shuffles the numbers around and doesn't change what those values are, it has the advantage that it works regardless of what format the original numbers are in (e.g. signed 32-bit integers, unsigned 64-bit integers, etc.)
On the other hand, let's suppose that we're working with signed integers (say, Java's int type). We know that we only care about the numbers 1, 2, 3, ..., n, which are all positive numbers. Therefore, the sign bit of those numbers will always be 0. We could therefore consider "stealing" that bit and, essentially, directly encoding our original bitvector idea in the input array. For example, suppose we have this input array:
Array: 3, 1, 4, 1, 5, 9, 2
Index: 0 1 2 3 4 5 6
We could scan across the input array. When we read a value x between 1 and n, we'll make the element at position x-1 a negative number by setting its sign bit. In this case, when we're done, that would look like this:
Array: -3, -1, -4, -1, -5, 9, 2
Index: 0 1 2 3 4 5 6
Now, we just need to find the first nonnegative value. The index of that value corresponds to the first bit that wasn't set in our bitvector (here, that's index 5), and so our answer would be one more than (5 + 1 = 6).
A complication here is that our input array can include negative numbers to begin with, and those existing negative numbers can mess up this approach by spuriously indicating missing numbers are present. Similarly, the number 0 will mess this up, since 0 = -0. One way to fix this is to reorder the numbers in the array so that all the nonpositive (negative and zero) values are stored at the end of the array, and the positive values go at the front. From there, we just pretend that we're dealing with the subarray formed from the positive values. (This is essentially the approach proposed by @pmcarpan and Harlan Gray.) Coding this up will require the use of an in-place partitioning algorithm to move things around. Fortunately, C++ has such an algorithm as part of its standard library, which means we could code it up like this:
int32_t first_missing_integer(std::vector<int32_t>& arr) {
/* Reorder the elements to put the positive elements at
* the front of the vector and the remaining elements
* at the back.
*/
auto boundary = std::partition(arr.begin(), arr.end(),
[](int32_t val) {
return val > 0;
});
/* The boundary position gives us the new "effective" length
* of the input array.
*/
size_t n = boundary - arr.begin();
/* Scan across the first n elements, using the sign bit
* of the appropriate array slots to store which items
* are present. Since we're making elements negative
* as we go, we need to work with the absolute values
* of the relevant elements. And fortunately, that will
* never cause an integer overflow, since we know all
* these values were positive to begin with.
*/
for (int32_t elem: arr) {
int32_t value = std::abs(elem);
/* The value must be between 1 and n for us to care
* about it, and the destination number needs to
* be positive for us to flip it.
*/
if (1 <= value && value <= n && arr[value] > 0) {
arr[value] *= -1;
}
}
/* Now, count from 1 to n to find the first missing value,
* which will be indicated by the first positive
* number.
*/
for (int32_t i = 1; i <= n; i++) {
if (arr[i - 1] > 0) {
return i;
}
}
/* Looks like all of them were present. The first missing
* integer is n + 1.
*/
return n + 1;
}
Hope this helps!
