Solution by fiony


  • 0
    F

    Approach #1 Brute Force [Accepted]

    Intuition

    Check all the positive numbers from 1 to N (N is the size of array) to see if it is missing in the array.

    Algorithm

    • Loop from 1 to N and check if it is found in the array, if not, return it.
    • Return N+1 if 1 ~ N are all found in the array.

    C++

    class Solution {
    public:
    	int firstMissingPositive(vector<int>& nums) {
            int N = nums.size();
            for(int i = 1; i <= N; i++)
            {
                bool found = false;
                for(int  j = 0; j < N; j++)
                {
                    if(nums[j]==i)
                    {
                        found = true;
                        break;
                    }
                }
                if(!found)
                    return i;
            }
            return N + 1;	
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n^2).
      To verify if a given positive number(i) is found in the array, we need to scan all of array member. Thus, it costs O(n) time. And we do this check for every number from 1 to N, so the total time cost is O(n^2)
    • Space complexity : O(1).
      We need a boolean flag and an integer, which occupy constant space.

    Approach #2 Use hashtable [Accepted]

    Algorithm

    • Construct a hashtable to store all the positive numbers in the array.
    • Then iterate positive numbers from 1 to N, return the first number not found in the hashtable.
    • Return N+1 if 1 to N are all found in the hashtable.

    C++

    class Solution {
    public:
    	int firstMissingPositive(vector<int>& nums) {
            unordered_set<int> nums_found;
            int N = nums.size();
            for(int i = 0; i < N; i++)
            {
                if(nums[i] > 0 && nums[i] <= N)
                    nums_found.insert(nums[i]);
            }
            for(int i = 1; i <= N; i++)
            {
                if(nums_found.find(i) == nums_found.end())
                    return i;
            }
            return N+1;	
        }
    }
    

    Complexity Analysis

    • Time complexity : O(2n)=O(n).
      To build the hashtable, we scan all the numbers in the array which cost O(n) time.
      To search a given number i in hash-table takes O(1) and we search from 1 to N which cost O(n) in total.
    • Space complexity : O(n).
      The hash-table has N element at most, which takes O(n) space.

    Approach #3 Use array index to hash [Accepted]

    Intuition
    Approach #2 use hashtable to reduce the time complexity to O(n) at the cost of extra O(n) space, is it possible to find a way to reuse the original array to reduce the space complexity?

    Noticed that the problem is asking to find the first missing positive, that is, we only need to hash the number from 1 to N (N is the array size), which enable us to use the original array as hashtable. (it is not straightforward to use original array index to hash those non-positive number and number larger than N)

    Algorithm

    • For a given positive number i in the array, it should be hashed and placed at the slot i.
    • After all the positive number (between 1 and N) in the array is hashed and placed at its correct slot, then we just need to scan from slot 1 and find the first slot i whose stored value is not i, and i is the first missing positive.
    • If such slot cannot be found, return N+1.

    The following diagram shows how this work.

    The Initial array is [9, 7, -1, 5, 2, 3, 1, 0, 6], with slots named from s1 to s9.
    For each iteration, the two element being swapped is highlighted with yellow background, the number in green is swapped to its hashed slot, and the number in red is waiting to be swapped to its hashed slot.
    0_1504020699936_FirstMissingPositive.PNG

    C++

    class Solution {
    public:
    	int firstMissingPositive(vector<int>& nums) {
            auto swap = [&](int i, int j)
            {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            };
            int N = nums.size();
            for(int i = 0; i < N; i++)
            {
                // nums[i] should be hashed to slot (nums[i] - 1)
                while(nums[i] > 0 && nums[i] <= N && nums[i] != nums[nums[i]-1])
                    swap(i, nums[i]-1);
            }
            for(int i = 0; i < N; i++)
            {
                if(nums[i] != i+1)
                    return i+1;
            }
            return N+1;
    }
    

    Complexity Analysis

    • Time complexity : O(2n) = O(n).

      • For the for-while loop, although it is a double loop, the total time is still O(n). Because for every iteration, we will place/swap the stored number at slot i at its expected 'hashed' slot, and this number won't be placed/swap again. Noticed in the above diagram, the while loop skip checking s3, s5-s9 because they are already placed correctly by previous iterations. And in worst case, we need to place at most N numbers to its hashed slot.
      • For the second for loop to scan the unmatched slot, it takes O(n) in worst case
    • Space complexity : O(1).
      we use the original array as a hashtable, and only use constant space to facilitate swaping and loop.


Log in to reply
 

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