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.

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

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 of pmcarpan's answer that runs in O(n) time and uses O(1) space.

def missing_int(nums: MutableSequence[int]) -> int:
    # If empty array or doesn't have 1, return 1
    if not next((x for x in nums if x == 1), 0):
        return 1

    lo: int = 0
    hi: int = len(nums) - 1
    i: int = 0
    pivot: int = 1

    while i <= hi:
        if nums[i] < pivot:
            swap(nums, i, hi)
            hi -= 1
        elif nums[i] > pivot:
            swap(nums, i, lo)
            i += 1
            lo += 1
        else:
            i += 1

    x = 0
    while x <= hi:  # hi is the index of the last positive number
        y: int = abs(nums[x])
        if 0 < y <= hi + 1 and nums[y - 1] > 0:  # Don't flip sign if already negative
            nums[y - 1] *= -1
        x += 1

    return next((i for i, v in enumerate(nums[:hi + 1]) if v >= 0), x) + 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