Given an array of integers, find the first missing positive integer in linear time and constant space

Question

In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same as below:

#include<bits/stdc++.h>
using namespace std;
int main(){
 int arr[]={1,-1,-5,-3,3,4,2,8};
 int size= sizeof(arr)/sizeof(arr[0]);
 sort(arr, arr+size);
 int min=1;
 for(int i=0; i<size; i++){
 if(arr[i]>min) break;
 if(arr[i]==min) min=min+1;
 }
 cout<<min;
 return 0;
}

Here, I am first sorting the array, and then traversing the array once. Before traversing the array, I have initialized a variable named "min" as 1. Now, while traversing the array, when we get an integer that is equal to min, we simply increment the value of min. This ensures that the min variable hold the latest least positive integer that has not occurred yet. Can you think of any better approach? Thanks in advance.

• Dillon Davis: You cannot sort the array in linear time with constant space.
• Henry: @DillonDavis actually you can if the range of numbers is bounded.
• Dillon Davis: @Henry, just googled it- counting sort does have an in-place variant. I stand corrected.
• Z .: actually you can, if the number are "special" (i.e. integers) stackoverflow.com/questions/2352313/…
• user202729: You should explicitly specify that the array is modifiable.

Answer 1

Assuming the array can be modified,

1. We divide the array into 2 parts such that the first part consists of only positive numbers. Say we have the starting index as 0 and the ending index as end(exclusive).

2. We traverse the array from index 0 to end. We take the absolute value of the element at that index - say the value is x.

   1. If x > end we do nothing.
   2. If not, we make the sign of the element at index x-1 negative. (Clarification: We do not toggle the sign. If the value is positive, it becomes negative. If it is negative, it remains negative. In pseudo code, this would be something like if (arr[x-1] > 0) arr[x-1] = -arr[x-1] and not arr[x-1] = -arr[x-1].)

3. Finally, we traverse the array once more from index 0 to end. In case we encounter a positive element at some index, we output index + 1. This is the answer. However, if we do not encounter any positive element, it means that integers 1 to end occur in the array. We output end + 1.

It can also be the case that all the numbers are non-positive making end = 0. The output end + 1 = 1 remains correct.

All the steps can be done in O(n) time and using O(1) space.

Example:

Initial Array: 1 -1 -5 -3 3 4 2 8
Step 1 partition: 1 8 2 4 3 | -3 -5 -1, end = 5

In step 2 we change the signs of the positive numbers to keep track of which integers have already occurred. For example, here array[2] = -2 < 0, it suggests that 2 + 1 = 3 has already occurred in the array. Basically, we change the value of the element having index i to negative if i+1 is in the array.

Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1

In step 3, if some value array[index] is positive, it means that we did not find any integer of value index + 1 in step 2.

Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
 The answer is 4 + 1 = 5

• Jhanak Didwania: Can you please explain it using an example?
• Jhanak Didwania: Solution works very well. If I am not wrong, it is an extension of the question, stating, finding the duplicates in an array in same time and space constraints. Very well explained. Thank you so much
• Jhanak Didwania: One case that is not handled in the above solution is when the array has all the non- positive integers. In that case, answer should be 1.
• Luis Aceituno: @yosemite_k because it may already have been toggled and be negative. For example if you have the input array [2,3], the first step would find a 2 and toggle the number at index 2-1=1, which would result in the array [2,-3]. In the next step, however, you would want to take a 3 and not a -3, hence the absolute.
• pmcarpan: @Kaushal28 In step 2.2 we do not toggle. Once the sign is negative, it remains negative. For [1,1], the 0-th index which was turned negative for the first 1 remains negative for the second 1. "make the sign of the element negative" implies that the sign remains negative, and accounts for both cases 1) when it is positive and 2) when it is already negative (where making the sign negative has no effect as the element is already negative). I definitely understand that the phrasing is causing some misinterpretation to occur while using the above to write the code, so I'll add a clarification.

Answer 2

This is actually a LeetCode problem that asks for O(n) time and O(1) space, so sorting the input or converting it to a set won't work. Here's a Python 3 implementation that runs in O(n) time and uses O(1) space. Basically, we try to put each element i in nums[i - 1].

def missing_int(self, nums: List[int]) -> int:
 i = 0
 n = len(nums)
 while i < n:
 j = nums[i]
 if 0 < j < n and j != nums[j - 1]:
 nums[i], nums[j - 1] = nums[j - 1], nums[i]
 else:
 i += 1
 return next((x + 1 for x in range(n) if nums[x] != x + 1), n + 1)

Tests:

def test_missing_int(self):
 assert func.missing_int([1, 2, 1, 0]) == 3
 assert func.missing_int([3, 4, -1, 1]) == 2
 assert func.missing_int([7, 8, 9, 11, 12]) == 1
 assert func.missing_int([1]) == 2
 assert func.missing_int([]) == 1
 assert func.missing_int([0]) == 1
 assert func.missing_int([2, 1]) == 3
 assert func.missing_int([-1, -2, -3]) == 1
 assert func.missing_int([1, 1]) == 2
 assert func.missing_int([1000, -1]) == 1
 assert func.missing_int([-10, -3, -100, -1000, -239, 1]) == 2
 assert func.missing_int([1, 1]) == 2

• Surt: And with tests too.
• Abhijit Sarkar: "Code without tests is bad code. It doesn't matter how well written it is; it doesn't matter how pretty or object-oriented or well-encapsulated it is. With tests, we can change the behavior of our code quickly and verifiably. Without them, we really don't know if our code is getting better or worse." - Michael Feathers, Working Effectively with Legacy Code.
• Albe: Q1:Is swap a python3 function? If not, nums[i], nums[hi] = nums[hi], nums[ii] also works. Q2: why is the elif nums[i] > pivot necessary?
• Abhijit Sarkar: @Albe swap isn't a Python built-in function, I missed to show it's implementation. As for the elif, what we are doing here is partition the input array into positive and negative numbers. If it's still not clear, I encourage you to use the given tests and a debugger to walk through the code.
• Abhijit Sarkar: @Albe Indeed, I've updated the code with a simpler implementation.

Answer 3

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.

1. 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.
2. 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!

• Metro Smurf: Whoa! This is like a mini thesis. Incredibly well explained and should be the newly accepted answer. Kudos!

Answer 4

PMCarpan's algorithm works.

I think your approach works, but you should specify the type of sort you're doing so that it is clear it is a linear sort and not necessarily a full sort of the entire array. This results in O(N) time without using any space.

Scan the array, as you're scanning if the value in your current index is less than the length of the array then swap it with the value currently in that index. You must continue swapping until it no longer makes sense to swap at each index. Then at the end do one more scan until you find an index that isn't correct.

Here's some working python code, although python is not the place to do this sort of thing, lol.

def sortOfSort(arr) :
 for index in range(len(arr)) :
 checkValue = arr[index]
 while(checkValue > 0 and checkValue != index and checkValue < len(arr) and arr[checkValue] != checkValue) :
 arr[index] = arr[checkValue]
 arr[checkValue] = checkValue
 checkValue = arr[index]
 return arr[1:] + [arr[0]]
def findFirstMissingNumber(arr) :
 for x in range(len(arr)) :
 if (x+1 != arr[x]) :
 return x+1
 return len(arr) + 1

the return arr[1:] part is because based on your description we aren't including zero as a starting point.

• Yonas Kassa: have you tested it with [3, 2, 1, 6, 5, 4] ?
• FredMan: @yosemite_k As this question was asked in 2018, I have no idea if I tested it on that or if I even tested it at all, but I've just now tested it and it produced "7" which I believe is the correct answer.
• Yonas Kassa: for me it produced "1"
• FredMan: There are two functions, you have to run the first function as input to the second. EG findFirstMissingNumber(sortOfSort([3, 2, 1, 6, 5, 4]))
• Yonas Kassa: I see, then it is better to modify the code to call sortOfSort inside findFirstMissing function

Answer 5

It is much simpler. (Solution is not mine)

public static int Missing(int[] a)
{
 // the idea is to put all values in array on their ordered place if possible
 for (int i = 0; i < a.Length; i++)
 {
 CheckArrayAtPosition(a, i);
 }
 for (int i = 0; i < a.Length; i++)
 if (a[i] != i + 1)
 return i + 1;
 return a.Length + 1;
}
private static void CheckArrayAtPosition(int[] a, int i)
{
 var currentValue = a[i];
 if (currentValue < 1) return; // do not touch negative values because array indexes are non-negative
 if (currentValue > a.Length) return; // do not touch values that are bigger than array length because we will not locate them anyway
 if (a[currentValue - 1] == currentValue) return; // do not need to change anything because index contain correct value already
 Swap(a, i, currentValue - 1);
 CheckArrayAtPosition(a, i); // now current position value is updated so we need to check current position again
}
private static void Swap(int[] a, int i, int j)
{
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

There is a recursion but since each Swap puts 1 value to the correct place there will be <= n swaps. Linear time

Answer 6

Here is a C implementation
INPUT

#include <stdio.h>
#include <stdlib.h>
//Here we separate the positive and negative number
int separate (int arr[], int size)
{
 int j = 0, i , temp;
 for(i = 0; i < size; i++)
 {
 if (arr[i] <= 0)
 {
 /*Here we using bitwise operator to swap the
 numbers instead of using the temp variable*/
 arr[j] = arr[j]^arr[i];
 arr[i] = arr[j]^arr[i];
 arr[j] = arr[j]^arr[i];
 j++;
 }
 }
 printf("First We Separate the negetive and positive number \n");
 for( i = 0 ; i <size ; i++)
 {
 printf("Array[%d] = %d\n",i,arr[i]);
 }
 return j;
}
int findMissingPositive(int arr[], int size)
{
printf("Remove the negative numbers from array\n");
int i;
for( i = 0 ; i <size ; i++)
{
 printf("Array[%d] = %d\n",i,arr[i]);
}
for(i = 0; i < size; i++)
{
 if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)
 arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];
}
for(i = 0; i < size; i++)
 if (arr[i] > 0)
 {
 return i+1;
 }
return size+1;
}
int findMissing(int arr[], int size)
{
int j = separate (arr, size);
return findMissingPositive(arr+j, size-j);
}
int main()
{
int size ;
printf("Enter the Value of Size of Array : ");
scanf("%d",&size);
int arr[size];
printf("Enter the values :\n");
for( int i = 0 ; i < size ; i++)
{
 printf("Array[%d] = ",i);
 scanf("%d",&arr[i]);
}
int missing = findMissing(arr,size);
printf("The smallest positive missing number is %d ", missing);
return 0;
}

---

OUTPUT

Enter the Value of Size of Array : 8
Enter the values :
Array[0] = 1
Array[1] = -1
Array[2] = -5
Array[3] = -3
Array[4] = 3
Array[5] = 4
Array[6] = 2
Array[7] = 8
First We Separate the negetive and positive number
Array[0] = -1
Array[1] = -5
Array[2] = -3
Array[3] = 1
Array[4] = 3
Array[5] = 4
Array[6] = 2
Array[7] = 8
Remove the negative numbers from array
Array[0] = 1
Array[1] = 3
Array[2] = 4
Array[3] = 2
Array[4] = 8
The smallest positive missing number is 5
Process returned 0 (0x0) execution time : 27.914 s
Press any key to continue.

---

 /*
 How work :
 [if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)
 arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];]
 before: arr = { 7, 3, 4, 5, 5, 3, 2}
 i == 0: arr[0] = 7
 arr[7-1] is 2 > 0 ~> negate
 arr = { 7, 3, 4, 5, 5, 3, -2}
 i == 1: arr[1] = 3
 arr[3-1] is 4 > 0 ~> negate
 arr = { 7, 3, -4, 5, 5, 3, -2}
 i == 2: arr[2] is -4 ~> abs for indexing
 arr[4-1] is 5 > 0 ~> negate
 arr = { 7, 3, -4,-5, 5, 3, -2}
 i == 3: arr[3] is -5 ~> abs for indexing
 arr[5-1] is 5 > 0 ~> negate
 arr = { 7, 3, -4, -5, -5, 3, -2}
 i == 4: arr[4] is -5 ~> abs for indexing
 arr[5-1] is -5 < 0 ~> print abs(-5) as duplicate
 i == 5: arr[5] is 3
 arr[3-1] is -4 < 0 ~> print abs(3) as duplicate
 i == 6: arr[6] is -2 ~> abs for indexing
 arr[2-1] is 3 > 0 ~> negate
 arr = { 7, -3, -4, -5, -5, 3, -2}
 indices of positive entries: 0, 5 ~> 1 and 6 not in original array
 indices of negative entries: 1, 2, 3, 4, 6 ~> 2, 3, 4, 5, 7 in original array
*/

• Graham Toal: It's easier if you move the negative values to the right instead of the left: #include <stdio.h> int main (void) { int data[] = { -9, 7, 5, 0, 6, 2000, 1, 3, -1, 1, 9, -9 }; int i=0, size = sizeof(data)/sizeof(*data); do { while ((data[i] <= 0) && (i <= (size-1))) data[i] = data[--size -1]; } while (++i < size); for (i = 0; i < size; i++) if (((1 <= data[i]) && (data[i] <= size)) && (data[data[i]-1] > 0)) data[data[i]-1] *= -1; size+=1; for (i = 1; i < size; i++) if (data[i-1] > 0) {size = i; break;} printf ("%d\n", size); fflush(stdout); return(0); }

Answer 7

Here's another python implementation with o(n) time complexity and o(1) space complexity

def segregate(arr):
 length = len(arr)
 neg_index = length
 for i, value in enumerate(arr):
 if(value < 1 and neg_index == length):
 neg_index = i
 if(neg_index != length and value >= 1):
 temp = arr[i]
 arr[i] = arr[neg_index]
 arr[neg_index] = temp
 neg_index += 1
 return arr[:neg_index]
def missingPositiveNumber(arr):
 arr = segregate(arr)
 length = len(arr)
 for i, value in enumerate(arr):
 if(value - 1 < l):
 arr[abs(value) - 1] = -(abs(arr[abs(value) - 1]))
 for i, value in enumerate(arr):
 if(value > 0):
 return i + 1
 return length + 1
print(missingPositiveNumber([1, -1, 2, 3]))

Answer 8

This is in Java. Time complexity f O(N) and space complexity O(1)

private static int minimum_positive_integer(int[] arr) {
 int i = 0;
 int j = arr.length - 1;
 //splitting array
 while (i < j) {
 if (arr[i] > 0) {
 i++;
 }
 if (arr[j] <= 0) {
 j--;
 }
 if (arr[i] <= 0 && arr[j] > 0) {
 int t = arr[i];
 arr[i] = arr[j];
 arr[j] = t;
 i++;
 j--;
 }
 }
 int len_positive = i;
 if (arr[i] > 0) len_positive++;
 for (i = 0; i < len_positive; i++) {
 int abs = Math.abs(arr[i]);
 if (abs <= len_positive) {
 int index = abs - 1;
 arr[index] = -abs;
 }
 }
 for (i = 0; i < len_positive; i++) {
 if(arr[i] > 0) return i + 1;
 }
 return len_positive + 1;
 }

Answer 9

Here is my answer accepted on leetcode

 def firstMissingPositive(self, nums):
 if 1 not in nums:
 return 1
 n = len(nums)
 for i in range(n):
 if nums[i] > n or nums[i] <= 0:
 nums[i] = 1
 for i in range(n):
 a = abs(nums[i])
 if a == n:
 nums[0] = -abs(nums[0])
 else:
 nums[a] = -abs(nums[a])
 for i in range(2, n):
 if nums[i] > 0: return i
 return n if nums[0] > 0 else n+1

Answer 10

Javascript implementation of PMCarpan's algorithm

function getMissingInt(array) {
 array = array.filter((a) => a > 0);
 for (let i = 0; i < array.length; i++) {
 const value = Math.abs(array[i]);
 if (value <= array.length && array[value - 1] > 0) {
 array[value - 1] *= -1;
 }
 }
 for (let i = 0; i < array.length; i++) {
 if (array[i] > 0) {
 return i + 1;
 }
 }
 return array.length + 1;
}
console.log(getMissingInt([1, -1, -5, -3, 3, 4, 2, 8]));
console.log(getMissingInt([3, 4, -1, 1]));
console.log(getMissingInt([1, 2, 0]));

With constant space and time:

function segregateItems(array) {
 let end = array.length - 1;
 for (let i = 0; i < end+1; i++) {
 if (array[i] <= 0) {
 [array[i], array[end]] = [array[end], array[i]];
 end--;
 }
 }
 return end + 1;
}
function getMissingInt(array) {
 let positiveListLength = segregateItems(array);
 for (let i = 0; i < positiveListLength; i++) {
 const value = Math.abs(array[i]);
 if (value <= positiveListLength && array[value - 1] > 0) {
 array[value - 1] *= -1;
 }
 }
 for (let i = 0; i < positiveListLength; i++) {
 if (array[i] > 0) {
 return i + 1;
 }
 }
 return positiveListLength + 1;
}
console.log(getMissingInt([1, -1, -5, -3, 3, 4, 2, 8]));
console.log(getMissingInt([3, 4, -1, 1]));
console.log(getMissingInt([1, 2, 0]));

• templatetypedef: The array.filter function returns a new array of values, which requires O(n) auxiliary storage space. This therefore doesn't use O(1) auxiliary space.
• templatetypedef: Correct me if I’m wrong, but doesn’t splice take time O(n) because it needs to shift down all elements after the removed one by one position? If so, that would make this run in time O(n^2).
• Shub: @templatetypedef yup agreed, added updated snippet along with older filter approach.

Answer 11

#Returns a slice containing positive numbers
def findPositiveSubArr(arr):
 negativeIndex = 0
 if i in range(len(arr)):
 if arr[i] <=0:
 arr.insert(negativeIndex, arr.pop(i))
 negativeIndex += 1
 return arr[negativeIndex:]
#Returns the first missing positive number
def findMissingPositive(positiveArr):
 l = len(positiveArr)
 for num in positiveArr:
 index = abs(num) - 1
 if index < 1 and positiveArr[index] > 0:
 positiveArr[index] *= -1
 for i in range(l):
 if positiveArr[i] > 0:
 return i+1
 return l+1
if __name__ == "__main__":
 arr = [int(x) for x in input().strip().split()]
 positiveSubArr = findPositveSubArr(arr)
 print(findMissingPositive(positiveSubArr))

• templatetypedef: The cost of performing arr.pop(i) is O(n), since all the other array elements have to shift down one position. This means that this code does not run in time O(n).

Answer 12

My solution in Python:

def lowest_positive(lista):
result = 0
dict = {}
for i in lista:
 if i <= 0:
 continue
 if i in dict:
 continue
 else:
 dict[i] = i
 if result == 0:
 result = result +1
 if result < i: 
 continue
 result = result +1
 while result in dict:
 result = result +1
return result

Test cases:

lista = [5, 3, 4, -1, 1, 2]
lista = [1,2,3,4,5]
lista = [3, 4, -1, 1]
lista = [2, 3, 4, 1]
lista = [1,0]
lowest_positive(lista)

Please note, I am not considering 0 as positive number

Logic: If number is less than 0, it is rejected. Then the number is checked in dictionary if it exist, if yes, the next number is read else it is added to the dictionary. result is the counter which is incremented one by one. if result is less than the number read in the list, the next number is read else, the counter is increased by one and this result is also checked in dictionary. Dictionary in all will store all the number read in the list, plus any missing positive numbers in between the smallest number read in the list.

• templatetypedef: This approach doesn't use O(1) storage space, since you need room for the dictionary.

Answer 13

Drawback of the above approach is it takes extra space for assigning "max_value" which is not the right solution

def missing_positive_integer(my_list):
 max_value = max(my_list)
 my_list = [num for num in range(1,max(my_list)) if num not in my_list]
 if len(my_list) == 0:
 my_list.append(max_value+1)
 return min(my_list)
my_list = [1,2,3,4,5,8,-1,-12,-3,-4,-8]
missing_positive_integer(my_list)

• templatetypedef: I don't believe this runs in linear time or uses constant auxiliary space. The list comprehension on the second line requires checking an array for membership, which takes time O(n), and does this n times. The resulting list also uses O(n) auxiliary storage space.

Answer 14

JavaScript:

let findFirstMissingNumber = ( arr ) => {
 // Sort array and find the index of the lowest positive element.
 let sortedArr = arr.sort( (a,b) => a-b );
 const lowestPositiveIndex = arr.findIndex( (element) => element > 0 );
 // Starting from the lowest positive element
 // check upwards if we have the next integer in the array.
 let i = lowestPositiveIndex;
 while( i < sortedArr.length ) {
 if ( sortedArr[ i + 1 ] !== sortedArr[ i ] + 1 ) {
 return sortedArr[ i ] + 1
 } else {
 i += 1;
 }
 }
 }
 console.log( findFirstMissingNumber( [3, 4, -1, 1, 1] ) ); // should give 2
 console.log( findFirstMissingNumber( [0, 1, 2, 0] ) ); // should give 3

• templatetypedef: The arr.sort function does not run in time O(n); because it's a comparison-based algorithm, it runs in time O(n log n).

Answer 15

I didn't test it in detail, but for sorted array here is how I would approach it, any improvements are welcome. constrains:

• linear time

• constant space

  solution:
  start with lowest positive integer (i.e. lpi <- 1)
  while parsing the array, if lpi is already in the array, increment it
  

lpi is now the lowest positive integer not available in the array

simple python function will be as follows:

def find_lpi(arr):
 lpi = 1
 for i in arr:
 if lpi == i:
 lpi += 1
 return lpi

if the array is unsorted, the following could be alternative solution.

first create a binary array, X, of zeroes with length max(arr). For each item in the array mark the index of the X, as 1 return the smallest index with 0

the following is a simple implementation satisfying

• linear time

• constant space complexity constraints.

  def find_lpi(arr):
   x = [0 for x in range(max(arr)+1)]
   for i in arr:
   x[i] = 1 
   for i in range(1,len(x)):
   if x[i] ==0:
   return i
   return len(x)
  

• Lasse V. Karlsen: It doesn't say that the array is sorted. If it was you can simply loop through it comparing two neighboring elements, if they're not N and N+1, something is missing between then.
• Yonas Kassa: for non sorted arrays, it needs a little more thought and a few more variables.

Answer 16

public int FindMissing(){
 var list = new int[] { 6, -6, 4, 5 };
 list = list.OrderBy(x => x).ToArray();
 var maxValue = 0;
 for (int i = 0; i < list.Length; i++)
 {
 if (list[i] <= 0)
 {
 continue;
 }
 if (i == list.Length - 1 ||
 list[i] + 1 != list[i + 1])
 {
 maxValue = list[i] + 1;
 break;
 }
 }
 return maxValue;
}

1. sort the data by ascending order:
2. for loop the data
   • if value less than equal to 0 then do nothing and skip.
   • check if the current index value plus 1 was equal to next index value
     • if yes, continue with the loop.
     • if no, current index value plus 1 will be the missing positive integer

• a.k: sorting is not linear in n (# of elements of the array)