# 41. First Missing Positive

Description:

https://leetcode.com/problems/first-missing-positive/#/description

Algorithm:

I used unordered_map.

Go through the array to record the max number and min number.

Code:
``` class Solution { public: int firstMissingPositive(vector& nums) { unordered_map <int, int> mapping; int maxNum = 0; int minNum = INT_MAX; for (int i = 0; i < nums.size(); i++) { mapping[nums[i]] = 1; if (nums[i] > maxNum) maxNum = nums[i]; if (nums[i] < minNum) minNum = nums[i]; } if (maxNum < 1 || minNum > 1) return 1; for (int i = 1; i < maxNum; i++) { auto it2 = mapping.find(i); if (it2 == mapping.end()) return i; } return maxNum + 1; } };```

Timing:

Beats 2.82% (:( ) 9ms

Best 3ms code:

``` class Solution { public: int firstMissingPositive(vector& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { while (nums[i] != i + 1) { if (nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1]) break; 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; } };```