41 First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in $$O(n)$$ time and uses constant space.

Solution

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

Notes
Put all valid numbers in "right position", s.t. nums[i] = i+1

• What if we have negative number?
• What if we have numbers larger than n? Leave them alone!

For a given position nums[i] in range $$[1,n]$$, check whether it is at the right position.

• If yes, continue with the loop;
• If not, swap it with nums[nums[i]-1], and repeat the procedure for the new nums[i], util it is not a valid number!
• note a tricky case

  nums[i] == nums[nums[i]-1]
  // nums[nums[i]-1] is already in the right position.
  

  Note to stop the loop to avoid an infinite loop.