30 Days of Code [Day 11]

24 Aug 2021

QUESTION : 41. First Missing Positive

VERY BAD SOLUTION with maps

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        map<int, bool> m;
        fv(nums){
            if(it > 0) m.insert(mp(it, false));
        }
        int i=1;
        fv(m){
            if(it.first != i) return i;
            i++;
        }
        return m.size()+1;
    }
};

OPTIMISED SOLUTION

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        fo(i,0,n){
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        fo(i,0,n){
            if(nums[i] != i+1) return i+1;
        }
        return n+1;
    }
};