41. First Missing Positive

day1.1

class Solution {
    public int firstMissingPositive(int[] nums) {
// Solution 1
        // int result = 1;
        // Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        // for(int i = 0; i < nums.length; i++ ){
        // map.put(nums[i],i);
        // }

        // for(int i = 1; i <= nums.length; i++ ){
        // if(!map.containsKey(i)){
        // result = i;
        // return result;
        // }
        // }
        // result = nums.length + 1;
        // return result;
// Solution 2
        // int result = 1;
        // Set<Integer> set = new HashSet<Integer>();

        // for (int i = 0; i < nums.length; i++) {
        //     set.add(nums[i]);
        // }

        // for (int i = 1; i <= nums.length; i++) {
        //     if (!set.contains(i)) {
        //         result = i;
        //         return result;
        //     }
        // }
        // result = nums.length + 1;
        // return result;

         for(int i = 0; i < nums.length; i++){
            while(nums[i] <= nums.length && nums[i] > 0 && nums[nums[i] - 1] != nums[i]){
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }

        return nums.length + 1;
    
    }
}