LeetCode 41 First Missing Positive

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

For example

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

Difficulty
Hard

Analysis

For an array with length of N (after removing all non-positive elements), our search range is [1, N+1] (positive starting from 1).

e.g.
For the case [1, 2, 0], we should search for a missing element in the range of [1, 2, 3].
For [3, 4, -1, 1], we should search for range of [1, 2, 3, 4]

Idea 1
Sort the array and search

Idea 2
Place the element at the according index position. The missing element at index i is what we found. e.g. place val = num at positoin of index = num-1 (put 4 at index 3) note that we only place the value that is possible to be the answer so that its index won't be out of bound of the array.

more cases:
[5, 6, 7], we should search for [1, 5, 6, 7]. Obviously, the missing element is 1. [5], we search for [1, 5], the missing element is 1. [-1], we search for [1], the missing element is 1. [1], we search for [1, 2], the missing element is 2 [2, 2], we search for [1, 2, 2], the missing element is 1.

Be careful with case [2, 2]. This is nums[i] = nums[nums[i]-1], we should skip this iteration.

Idea 3
Tag the index of the visited element, the index that are not taged ever is the answer.

Summary

If an un-sorted array needs O(n) time, it is usually to apply hash table. For constant space, we could use the array itself as a "hash table". nums[0] = 1, nums[1] = 2, ... nums[n-1] = n We place num to index num - 1 as possible as we can. If nums[i] != i + 1, i + 1 is the value we are missing.

Solutions

1. Cpp solution 3ms

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        int i = 0;
        while(i < n) {
            if(nums[i] > 0 && nums[i] <= n && nums[i] != i+1 && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
            else
                i++;
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

1. Go solution 6ms

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; {
        if (nums[i] > 0 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
            nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
        } else {
            i++
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i + 1 {
            return i + 1
        }
    }
    return n + 1
}

1. Python solution 65ms

class Solution(object):
    def firstMissingPositive(self, nums):
        if not nums:
            return 1
        i = 0
        length = len(nums)
        while i < length:
            current = nums[i]
            if current <= 0 or current > length or nums[current - 1] == current:
                i += 1
            else:
                nums[current - 1], nums[i] = nums[i], nums[current - 1]

        for i in range(length):
            if nums[i] != i + 1:
                return i + 1
        return length + 1

Reference