My short c++ solution, O(1) space, and O(n) time


  • 358

    Put each number in its right place.

    For example:

    When we find 5, then swap it with A[4].

    At last, the first place where its number is not right, return the place + 1.

    class Solution
    {
    public:
        int firstMissingPositive(int A[], int n)
        {
            for(int i = 0; i < n; ++ i)
                while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
                    swap(A[i], A[A[i] - 1]);
            
            for(int i = 0; i < n; ++ i)
                if(A[i] != i + 1)
                    return i + 1;
            
            return n + 1;
        }
    };

  • 0
    H

    Really good solutoins. Thanks for sharing.


  • 0
    P

    Very interesting method to do it.


  • 0
    S

    truly smart!!!!


  • 14
    C

    smart solution, but time complexity is not O(n)


  • 0
    A

    really smart way, thanks for sharing


  • 28

    We visit each number once, and each number will be put in its right place at most once, so it is O(n) + O(n). Although there are two nesting of cyclic (for and while), but its time complexity is still O(n).


  • 2
    R

    i don't think the time complexity this way is O(n), since each number we visit more than once, the outer for loop traverse each number even we swap the number before, so the time complexity is O(n^2)?


  • 3

    But the "for" loop and "while" loop will visit each elem at most twice together.


  • 2
    E

    Since we only see each element at most twice as @makuiyu mentioned, the time complexity should be O(2n) = O(n). Sometimes we might see some negative numbers more than twice, but when that happens we will only see the positive number we swapped with that negative number once. In conclusion, it is equivalent we see all the positive number twice and negative number once. Let's assume k is the number of the positive numbers in the array, where k < n. The time complexity is O(2k + n - k) = O(n + k), where worst case is O(2n) = O(n).


  • 1
    N

    what if the array has duplicates? Will this still work?


  • 3

    Sure!
    When it has duplicates, such as two 'x'. The first will be put into A[x-1]. And then the second 'x' will make 'A[x - 1] != x' false.


  • 0
    Z

    It is amazing!!


  • 0
    Y

    very beautiful code, thx!


  • 0
    Y

    nice solution and clear explanation! Thank you!


  • 2
    L

    Will this work if the input array contains very big numbers? And especially gaps, something like this: -255567, 0, 255678, 3123343, etc..


  • 13

    Hi, makuiyu. Thanks for your sharing. Since the C++ interface on the OJ has changed from int A[], int n to vector<int>& nums, I rewrite the code below.

    class Solution {
    public: 
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size(); 
            for (int i = 0; i < n; i++)
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                    swap(nums[i], nums[nums[i] - 1]);
            for (int i = 0; i < n; i++)
                if (nums[i] != i + 1)
                    return i + 1;
            return n + 1;
        }
    };

  • 0
    S
    This post is deleted!

  • 1
    R

    Yes, for your case (take your numbers above), it will skip the first for loop, and directly runs the second loop, so 1 will be returned at the end.


  • 1
    S

    Hi, makuiyu, this method seems very similar as bubble sort. Is the time complexity O(n*n)?


Log in to reply
 

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