11.First Missing Positive

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

Example 1:
Input: nums = [1,2,0]
Output: 3

Example 2:
Input: nums = [3,4,-1,1]
Output: 2


Example 3:
Input: nums = [7,8,9,11,12]
Output: 1

Solution: (Hash set)

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {

        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++)
        {
            s.insert(nums[i]);
        }

        for (int i = 1; i < INT_MAX; i++)
        {
            if (s.find(i) == s.end())
            {
                return i;
            }
        }

        return 0;
    }
};

Time Complexity: O(n) Space Complexity: O(n)

Solution:

Algorithm: Creating an array of all positive numbers Iterate and mark the index of a each number as -ve Finally, a number which is not negative is the missing number.

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {

        vector<int> v;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] > 0)
            {
                v.push_back(nums[i]);
            }
        }

        for (int i = 0; i < v.size(); i++)
        {
            int index = abs(v[i]) - 1;

            if (index < v.size() && v[index]>0)
            {
                v[index] = -1 * v[index];
            }
        }

        for (int i = 0; i < v.size(); i++)
        {
            if (v[i] > 0)
            {
                return i + 1;
            }
        }
        return v.size() + 1;
    }
};

Time Complexity: O(n) Space Complexity: O(n)

Solution:

Algorithm: Using positive number each number as index

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {

        int n = nums.size();
        int start = 0;

        while (start < nums.size())
        {
            if (nums[start] > 0)
            {
                int index = nums[start] - 1;
                if (index >= 0 && index < n && nums[index] != index + 1)
                {
                    swap(nums[start], nums[index]);
                }
                else
                {
                    start++;
                }
            }
            else
            {
                start++;
            }
        }

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

        return n + 1;
    }
};

Time Complexity: O(n) Space Complexity: O(1)