41 First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example, Given[1,2,0]return3, and[3,4,-1,1]return2.

Your algorithm should run inO(n) time and uses constant space.

The Idea: The goal was to achieve this in O(n) time and O(1) space. Using the same array, we can hash the elements of the array to its correct location. e.g. array[0] = array[array\[0]]. We can ignore all negative numbers because we are interested in the first positive. That is, the idea is to search for 1, then 2... and so fourth. For similar reasons, we can ignore values that are greater than the magnitude of the array because they are guaranteed to not be the first positive anyway, since the array can only hold as much as its greatest length.

If these conditions are valid, we swap array[i] with array[array[i]] making it so array[i] hashes to its correct position in the array. Once this process is complete, we are guareenteed to know that all the elements should be moved to their correct location within the array. If they have not otherwise, then its a guareentee they are missing as the first positive.

So we go through another for loop at the end to look for this first instance. I probabily can make this a lot cleaner looking, but it runs in linear time and constant space.

Complexity: O(n) time and O(1) space

int firstMissingPositive(vector<int>& nums)
{
    if (nums.empty()) return 1;
    else if (nums.size() == 1) {
        if (nums[0] <= 0 || nums[0] > 1)
            return 1;
        else if (nums[0] == 1) return 2;
    }

    const size_t n_size = nums.size();

    for (int i = 0; i < n_size; i++) {
        while (1) {
            if (nums[i] < 0 || nums[i] >= n_size || i == nums[i]) break;
            if (nums[i] == nums[nums[i]]) break;
            swap(nums[i], nums[nums[i]]);
        }
    }

    int i;
    for (i = 1; i < n_size; i++) {
        if (nums[i] != i) return i;
    }
    if (nums[0] == nums[i - 1] + 1) return nums[0] + 1;
    return nums[i - 1] + 1;
}

Approach 2 using extra space:

The Idea: Throw all the numbers into a hashset. Find the minimum and then maximum. Then first the first element before or after the minimum until the element is found.

Complexity: O(n) time and O(n) space

import sys


class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if not nums:
            return 1

        # for find later and terminating condition
        hashset = set(nums)
        maxx = max(nums)

        # find min value after 0
        minn = sys.maxsize
        for i, num in enumerate(nums):
            if num < minn and num > 0:
                minn = num
        # if not found, or 1 doesnt exist then first positive has to be 1
        if minn == sys.maxsize or 1 not in hashset:
            return 1
        # dont assume to look forward after minimum e.g. [1,3,4,-1] -> 2 not 5 
        elif minn > 1 and minn - 1 not in hashset:
            return minn - 1

        # otherwise try to find after the minimum
        # find the first missing after min
        while minn <= maxx:
            minn += 1
            if minn not in hashset:
                return minn
        return minn

Testing

obj = Solution()
print(obj.firstMissingPositive([1,3, 1000, -1])) # 2
print(obj.firstMissingPositive([4,3, 1000, -1])) # 1
print(obj.firstMissingPositive([-20, -15, -1]))  # 1
print(obj.firstMissingPositive([1,2, 1000, -1])) # 3
print(obj.firstMissingPositive([1000,-1]))       # 1
print(obj.firstMissingPositive([2]))             # 1
print(obj.firstMissingPositive([1]))             # 2
print(obj.firstMissingPositive([2,3]))           # 1
print(obj.firstMissingPositive([3,4]))           # 2
print(obj.firstMissingPositive([1, 2, 3] ))      # 4
print(obj.firstMissingPositive([3, 2, 1]))       # 4
print(obj.firstMissingPositive([-1, 0, -20]))    # 1
print(obj.firstMissingPositive([1, 5, 6, 20]))   # 2
print(obj.firstMissingPositive([0]))             # 1