Problem description:

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2
Input: [1,2,0]
Output: 3

Example 2:

1
2
Input: [3,4,-1,1]
Output: 2

Example 3:

1
2
Input: [7,8,9,11,12]
Output: 1

Note:

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

Solution:

The idea of this question is we can traverse the whole array once, putting every element in a slot.
So, how do we know where we should put this element?

Let’s check and observe the example.

  1. Input: [1,2,0]
  • Zero and negative number does not count: The question is asking for missing positive number.
  • we can put the number nums[i] in slot i-1
  1. Input: [3,4,-1,1]
    [-1,4,3,1]
    [-1,1,3,4]
    Output: 2
  • if we put the numbers into the slot that we observed earlier, we can get [-1,1,3,4]; however, if we stop here, 1 is not in the right place. Therefore, we need to keep swapping until the ith element contains correct number or a zero/negative number.
  1. Input: [7,8,9,11,12]
    Output: 1
  • every element in the array exceed the size of array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        /*
        Thoughts:
        Since we can only do it in O(n) time, ony way to put all elements in order is to traverse all element once
        We can put n in A[n-1] slot
        Then walk through the array, if the number in A[n-1] is not n, then return it
        */
        
        //[1,2,0]
        for(int i= 0; i< nums.size(); i++){
            //
            while(nums[i]> 0 && nums[i]<= nums.size() && nums[nums[i]-1] != nums[i])
                swap(nums[i], nums[nums[i]-1]);
        }
        
        for(int i= 0; i< nums.size(); i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return nums.size()+1;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/Rq1yXX