Hashing: Given an array, find the first missing positive number

Problem Statement:

You are given an array, you need to return the first smallest positive integer.

You need to do it in O(n) and O(1) space.

Example:

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

Solution Explanation:

Solution is very simple.

We will make use of hash table to solve the problem.

Iterate through the array and add each element into the hash map.

For each number “i”, check if “i” exist in map, if present move to the next element, if not found return the element.

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

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;

int solution(vector<int>& nums) 
{
    int n = nums.size();
    unordered_map<int,bool> mp;


    int maxEle = *max_element(nums.begin(), nums.end());

    for(auto &num : nums)
    {
        mp[num] = true;
    }

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

    return maxEle < 0 ? 1 : maxEle+1;
}

int main()
{
    vector<int> arr = {1, 2, 0};
    cout<< solution(arr);

    return 0;
}

Output

3