share my solution O(n) time, O(1) space


  • 0
    Y

    '''
    class Solution {

    public:

    int firstMissingPositive(vector<int>& nums) {
    
        for (auto& u : nums) {
            if (u <= 0) u = nums.size() + 2;
        }
        for (auto& u : nums) {
            if (abs(u) <= nums.size()) {
                nums[abs(u) - 1] = -abs(nums[abs(u) - 1]);
            }
        }
        for (size_t i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) return i + 1;
        }
        return  nums.size() + 1;
    }
    

    };
    '''


  • 1
    O

    This is awesome. For first timers who didn't quite get technique at a first glance, here is an explanation:

    • We need to find the first positive integer that is missing in the array. For that, we need to start counting from 1 to n and see if any number is in the array, the moment that it is not, we have found the solution. (This might be counter intuitive to those who assume that we need the first element after the minimum one in the array - I made that mistake myself).

    • How to determine n? Well, we know that the array has a size, so we will count up to the size in the array. Why? Because if the array can hold n numbers, if it contains each element from 1 to n, then we know it does not contain n + 1 (which would be our solution). If it does not contain any one element from 1 to n, then we know the solution is in 1 to n.

    • When iterating from 1 to n, we need to determine if i is in the array. To do this, we are first going to iterate over the array beforehand, and use the values in the array as indices, marking in each index if the value of such index is in the array (more on this later). Since there might be negative values (which we don't care about), we first have to discard them by making them the size of the array + 2.

    • Once the array is sanitized, we can use the values in the array as indices, and mark in the location of each index we see, that it has been seen by making the value negative. We obviously do this if the index found is less than the array size. Since there might be repeated values, we use absolute function.

    • Now we can just go over 1 to n and see if the value in the array is not negative, if that is the case we return the first one we find. If from 1 to n this doesn't happen, we return n +1.


Log in to reply
 

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