lc-41

//Given an unsorted integer array nums, return the smallest missing positive int
//eger. 
//
// You must implement an algorithm that runs in O(n) time and uses constant extr
//a space. 
//
// 
// Example 1: 
// Input: nums = [1,2,0]
//Output: 3
// Example 2: 
// Input: nums = [3,4,-1,1]
//Output: 2
// Example 3: 
// Input: nums = [7,8,9,11,12]
//Output: 1
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5 * 105 
// -231 <= nums[i] <= 231 - 1 
// 
// Related Topics Array Hash Table 
// 👍 10299 👎 1387



//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> treeSet = new TreeSet<>();
        for (int num : nums) {
            if (num > 0) {
                treeSet.add(num);
            }
        }

        int last = 0;

        for (Integer value : treeSet) {
            if (value - last > 1) {
                return last + 1;
            }
            last = value;
        }

        return last + 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)