41. First Missing Positive

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

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

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

Solution

Approach 1: sorting takes either too much space or too much time, so can only try modifying the nums in place. Try to put the nums in their right place, but leave bad elements in there, and use a second pass to check.

Code (Python)

Approach 1:

    def firstMissingPositive(self, nums: List[int]) -> int: 
        # idea: also try to put the nums in their right place, but leave bad things in there, and use a second pass to check
        for i in range(len(nums)):
            while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
                self._swap(i, nums[i] - 1, nums)
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

    def _swap(self, ind1, ind2, nums):
        temp = nums[ind1]
        nums[ind1] = nums[ind2]
        nums[ind2] = temp

Code (C++)

Approach 1:

// Swap the elements to the right positions.
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i)
        {
            long j = long(nums[i]) - 1;
            while (j >= 0 && j < nums.size() && nums[j] != nums[i])
            {
                std::swap(nums[j], nums[i]);
                j = nums[i] - 1;
            }
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return nums.size() + 1;
    }
};

// Mark the positions if the corresponding elements exist.
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] <= 0)
                nums[i] = nums.size() + 1;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            int j = std::abs(nums[i]) - 1;
            if (j < nums.size() && nums[j] > 0)
                nums[j] = 0 - nums[j];
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] > 0)
                return i + 1;
        }
        return nums.size() + 1;
    }
};