O(n) time, O(1) space 6ms simplest/shortest solution (IMO)


  • 0
    I
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            int n=nums.size(),first=1;
            for(int i=0; i<n; i++) {
                if (nums[i]==first) first++;
            }
            return first;
        }
    };
    

    The Idea is to first sort the array to get the numbers in non-decreasing order. If we find the first positive value, first (which is initially 1), we increment it and are searching for it next.
    Last value of first is the answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.