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

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

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

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.