Problem statement

Given an array of integers, find the first missing positive integer in linear time and constant space. 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.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

Approach

Before solving the problem let’s look a closer look at the input and problem statement, it states that we have an array of integer (may contain negative, positive and duplicate) and we have to find lowest missing positive integer Let’s collect useful information out of that

• we have to find the lowest missing positive number
• the missing number must belong to the range of 1 to the Array length
• All number that is either less than 1 and greater than Array length is of no use
• we can’t use extra space and have to solve the problem in linear time

Now to solve this problem, if we are able to move all number to its index position (e.g. if the number is 4 its position is 3^rd index), we can find which number is missing easily.

Now let’s place all number by traversing array to its index position.

Time for Code

def correct_position(nums, num):
    reserve_num = nums[num-1]
    nums[num-1] = num
    if not (reserve_num <=0 or reserve_num >= len(nums) or nums[reserve_num-1] == reserve_num):
        correct_position(nums, reserve_num)

def find_missing(nums):
    for i in range(len(nums)):
        correct_position(nums, nums[i])
    for i in range(len(nums)):
        if nums[i] != i+1:
            return i+1
            
# Code testing
assert find_missing([3, 4, -1, 1]) == 2
assert find_missing([1, 2, 0]) == 3